Note that in the sum
$$=\sum_{S_1=\pm 1}...\sum_{S_N=\pm 1}\langle S_2| T_{_{NN}}^{\dagger}|S_1\rangle\langle S_1| T_{_{NNN}}|S_3\rangle\langle S_3| T_{_{NN}}^{\dagger}| S_2\rangle\langle S_2| T_{_{NNN}}|S_4\rangle...\langle S_1| T_{_{NN}}^{\dagger}|S_N\rangle\langle S_N| T_{_{NNN}}|S_2\rangle$$
every pair $|S_i\rangle\langle S_i|$ occurs twice with some operator/matrix between them. So you cannot simply execute the sum over $S_i = \pm1$ for both occurrences separately.
As pointed out in the paper you linked, one solution via transfer matrix is to group two neighbouring spins to one 4-state spin. Then the problem can be reduced to NN interactions only.
You ask
how can you formally go from the summation over $s$ to the double sum over $s_1$ and $s_2$?
As we'll see in a moment, passing to the double sum relies on the mathematical fact (about tensor products of Hilbert spaces) that if $s_1$ labels a basis of states for system $1$, and if $s_2$ labels a basis of states for system $2$, then the set of all pairs $(s_1, s_2)$ labels a basis of states for the composite system.
Let's assume that the system at hand is a quantum system described by a state space (Hilbert space) $\mathcal H$. Let the (state) labels $s$ index an orthonormal basis of $\mathcal H$ consisting of eigenvectors $|s\rangle$ of the total system's Hamiltonian $H$;
\begin{align}
H|s\rangle = E(s)|s\rangle,
\end{align}
then the partition function is obtained by summing over these states;
\begin{align}
Z = \sum_s e^{-\beta E(s)}.
\end{align}
Notice that the state labels $s$ don't have to be numbers. They could, for example, be pairs of numbers or triples of numbers, whatever is most convenient to label the possible states for the system at hand.
Now, suppose that the system consists of a pair of subsystems $1$ and $2$, then the Hilbert space of the combined system can be written as a tensor product of the Hilbert spaces for the individual subsystems;
\begin{align}
\mathcal H = \mathcal H_1\otimes \mathcal H_2.
\end{align}
Let $H_1$ denote the hamiltonian for subsystem $1$, and let $H_2$ denote the hamiltonian for subsystem $2$. Let $\{|1, s_1\rangle\}$ be an orthonormal basis for $\mathcal H_1$ consisting of eigenvectors of $H_1$, and let $\{|2, s_2\rangle\}$ be an orthonormal basis for $\mathcal H_2$ consisting of eigenvectors of $H_2$, then we have the following basic fact;
The tensor product states
\begin{align}
|s_1, s_2\rangle := |1,s_1\rangle\otimes|2,s_2\rangle
\end{align}
yield an orthonormal basis for the full state space $\mathcal H = \mathcal H_1\otimes \mathcal H_2$.
In particular, the set of states one needs to sum over in the partition function can be enumerated by pairs $s=(s_1, s_2)$. Moreover, if the systems are non-interacting, then the Hamiltonian of the full system is essentially the sum of the Hamiltonians of the individual subsystems (with appropriate identity operator factors);
\begin{align}
H = H_1\otimes I_2 + I_1\otimes H_2,
\end{align}
so that if $E_1(s_1)$ and $E_2(s_2)$ denote the energy eigenvalues of $H_1$ and $H_2$ corresponding to the states $|1,s_1\rangle$ and $|2, s_2\rangle$, then the energy $E(s_1, s_2)$ of a tensor product basis state is their sum;
\begin{align}
H|s_1,s_2\rangle = E(s_1, s_2)|s_1, s_2\rangle = \big(E_1(s_1) + E_2(s_2)\big)|s_1,s_2\rangle,
\end{align}
and the partition function can be written as a sum over the tensor product basis states;
\begin{align}
Z = \sum_{(s_1,s_2)} e^{-\beta E(s_1, s_2)} = \sum_{s_1}\sum_{s_2} e^{-\beta\big(E_1(s_2) + E_2(s_2)\big)} = \sum_{s_1} e^{-\beta E_1(s_1)} \sum_{s_2} e^{-\beta E(s_2)} = Z_1Z_2
\end{align}
where in the second equality we have used the fact that a single sum over all possible pairs $(s_1, s_2)$ is equivalent to iterated sums over the possible values of $s_1$ and $s_2$.
Best Answer
$\newcommand{\e}{\boldsymbol=}$ $\newcommand{\p}{\boldsymbol+}$ $\newcommand{\m}{\boldsymbol-}$ $\newcommand{\gr}{\boldsymbol>}$ $\newcommand{\les}{\boldsymbol<}$ $\newcommand{\greq}{\boldsymbol\ge}$ $\newcommand{\leseq}{\boldsymbol\le}$ $\newcommand{\plr}[1]{\left(#1\right)}$ $\newcommand{\blr}[1]{\left[#1\right]}$ $\newcommand{\lara}[1]{\langle#1\rangle}$ $\newcommand{\lav}[1]{\langle#1|}$ $\newcommand{\vra}[1]{|#1\rangle}$ $\newcommand{\lavra}[2]{\langle#1|#2\rangle}$ $\newcommand{\lavvra}[3]{\langle#1|\,#2\,|#3\rangle}$ $\newcommand{\x}{\boldsymbol\times}$ $\newcommand{\qqlraqq}{\qquad\boldsymbol{-\!\!\!-\!\!\!-\!\!\!\longrightarrow}\qquad}$
Consider two complex $n\m$vectors expressed also as kets \begin{equation} \mathbf x\e \begin{bmatrix} x_1 \vphantom{\dfrac{a}{b}}\\ x_2 \vphantom{\dfrac{a}{b}}\\ \vdots \vphantom{\dfrac{a}{b}}\\ x_n \vphantom{\dfrac{a}{b}}\\ \end{bmatrix}\e \vra{\mathbf x}\qquad \texttt{and} \qquad \mathbf y\e \begin{bmatrix} y_1 \vphantom{\dfrac{a}{b}}\\ y_2 \vphantom{\dfrac{a}{b}}\\ \vdots \vphantom{\dfrac{a}{b}}\\ y_n \vphantom{\dfrac{a}{b}}\\ \end{bmatrix}\e \vra{\mathbf y}\quad \in \mathbb C^n \tag{01}\label{01} \end{equation} Complex conjugating and transposing these one-column matrices we obtain the bras \begin{equation} \mathbf x^{\boldsymbol*}\e \begin{bmatrix} \overline x_1 & \overline x_2 & \cdots & \overline x_n \vphantom{\dfrac{a}{b}}\\ \end{bmatrix}\e \lav{\mathbf x}\quad \texttt{and} \quad \mathbf y^{\boldsymbol*}\e \begin{bmatrix} \overline y_1 & \overline y_2 & \cdots & \overline y_n \vphantom{\dfrac{a}{b}}\\ \end{bmatrix}\e \lav{\mathbf y} \tag{02}\label{02} \end{equation} Their usual inner product in $\,\mathbb C^n\,$ is \begin{equation} \overline x_1\,y_1\p\overline x_2\,y_2\p\cdots\overline x_n\,y_n\e \begin{bmatrix} \overline x_1 & \overline x_2 & \cdots & \overline x_n \vphantom{\dfrac{a}{b}}\\ \end{bmatrix} \begin{bmatrix} y_1 \vphantom{\dfrac{a}{b}}\\ y_2 \vphantom{\dfrac{a}{b}}\\ \vdots \vphantom{\dfrac{a}{b}}\\ y_n \vphantom{\dfrac{a}{b}}\\ \end{bmatrix}\e \lavra{\mathbf x}{\mathbf y} \tag{03}\label{03} \end{equation} Given a $\,n\times n\,$ complex matrix $\,\mathrm A\,$ \begin{equation} \mathrm A\e \begin{bmatrix} a_{11} & a_{11} & \cdots & a_{1n} \vphantom{\dfrac{a}{b}}\\ a_{21} & a_{22} & \cdots & a_{2n} \vphantom{\dfrac{a}{b}}\\ \vdots & \vdots & \vdots & \vdots\vphantom{\dfrac{a}{b}}\\ a_{n1} & a_{n2} & \cdots & a_{nn}\vphantom{\dfrac{a}{b}}\\ \end{bmatrix} \tag{04}\label{04} \end{equation} the notation $\,\lavvra{\mathbf x}{\mathrm A}{\mathbf y}\,$ is the inner product of the vectors $\,\mathbf x\,$ and $\,\mathrm A\mathbf y\,$ expressed by matrices as \begin{equation} \lavvra{\mathbf x}{\mathrm A}{\mathbf y}\e \begin{bmatrix} \overline x_1 & \overline x_2 & \cdots & \overline x_n \vphantom{\dfrac{a}{b}}\\ \end{bmatrix} \begin{bmatrix} a_{11} & a_{11} & \cdots & a_{1n} \vphantom{\dfrac{a}{b}}\\ a_{21} & a_{22} & \cdots & a_{2n} \vphantom{\dfrac{a}{b}}\\ \vdots & \vdots & \vdots & \vdots\vphantom{\dfrac{a}{b}}\\ a_{n1} & a_{n2} & \cdots & a_{nn}\vphantom{\dfrac{a}{b}}\\ \end{bmatrix} \begin{bmatrix} y_1 \vphantom{\dfrac{a}{b}}\\ y_2 \vphantom{\dfrac{a}{b}}\\ \vdots \vphantom{\dfrac{a}{b}}\\ y_n \vphantom{\dfrac{a}{b}}\\ \end{bmatrix} \tag{05}\label{05} \end{equation} Under this spirit you could look at the $\,S_k\,$ as $2\times 1$ matrices and more precisely \begin{equation} S_k\e \left. \begin{cases} \begin{bmatrix} 1 \vphantom{\dfrac{a}{b}}\\ 0 \vphantom{\dfrac{a}{b}}\\ \end{bmatrix} \texttt{for} \p 1\\ \\ \begin{bmatrix} 0 \vphantom{\dfrac{a}{b}}\\ 1 \vphantom{\dfrac{a}{b}}\\ \end{bmatrix} \texttt{for} \m 1 \end{cases}\right\} \tag{06}\label{06} \end{equation} (note : this reminds us the up and down states of a spin-1/2 particle or the up and down quarks of isospin-1/2 particle).
So if for example $\,S_3\e\m 1\,$ and $\,S_8\e\p 1\,$ then \begin{equation} \lavvra{S_3}{\mathrm T}{S_8}\e \begin{bmatrix} 0 & 1 \vphantom{\dfrac{a}{b}}\\ \end{bmatrix} \begin{bmatrix} t_{11} & t_{11} \vphantom{\dfrac{a}{b}}\\ t_{21} & t_{22} \vphantom{\dfrac{a}{b}} \end{bmatrix} \begin{bmatrix} 1 \vphantom{\dfrac{a}{b}}\\ 0 \vphantom{\dfrac{a}{b}} \end{bmatrix}\e \begin{bmatrix} 0 & 1 \vphantom{\dfrac{a}{b}}\\ \end{bmatrix} \begin{bmatrix} t_{11} \vphantom{\dfrac{a}{b}}\\ t_{21} \vphantom{\dfrac{a}{b}} \end{bmatrix}\e t_{21} \tag{07}\label{07} \end{equation} For the rest look in the other till now two answers.