Are you sure we don't need $q_{n+1}$?

Since $p_{k+1} \equiv -p_k^2 \equiv p_k \pmod{2}$ and $q_{k+1} \equiv p_k^2 \equiv p_k \pmod{2}$, by simple induction $p_k$ and $q_k$ are odd for all $k$. Further, by the Euclidean Algorithm we have $$\gcd(p_{k+1},q_{k+1})=\gcd(2q_k^2-p_k^2,2q_k^2+p_k^2)=\gcd(2q_k^2-p_k^2,2p_k^2)=\gcd(2q_k^2,p_k^2,p_k^2)=\gcd(2q_k^2,p_k^2)=\gcd(q_k,p_k)^2,$$so by induction $p_k$ and $q_k$ are coprime for any $k$, where the third and fifth equalities come from the fact that $p_k$ and $q_k$ are odd. We now have the following two claims: Claim 1: $p_{m+i} \equiv p_ip_m^{2^i} \pmod{q_m}$ and $q_{m+i} \equiv q_ip_m^{2^i} \pmod{q_m}$ for all $i \geq 1$, except for $p_{m+1} \equiv -p_1p_m^{2^1} \pmod{q_m}$. Proof: This is by induction on $i$. It is easy to check this for $i=1,2$ (with the exception detailed). Now, using the inductive hypothesis, we have \begin{align*} p_{m+(i+1)} = 2q_{m+i}^2-p_{m+i}^2 \equiv 2(p_iq_m^{2^i})^2-(q_iq_m^{2^i})^2 =q_m^{2^{i+1}}(2p_i^2-q_i^2) =p_{i+1}q_m^{2^{i+1}} &\pmod{p_m}\\ q_{m+(i+1)} = 2q_{m+i}^2+p_{m+i}^2 \equiv 2(p_iq_m^{2^i})^2+(q_iq_m^{2^i})^2 =q_m^{2^{i+1}}(2p_i^2+q_i^2) =q_{i+1}q_m^{2^{i+1}} &\pmod{p_m}, \end{align*}hence proved. Claim 2: $p_{n+i} \equiv 2^{2^i}p_iq_n^{2^i} \pmod{p_n}$ and $q_{n+i} \equiv 2^iq_iq_n^{2^i} \pmod{p_n}$ for all $i \geq 1$. Proof: Again, we use induction on $i$, with the base case of $i=1$ being clear. Now, by the inductive hypothesis, \begin{align*} p_{n+(i+1)} =2q_{n+i}^2-p_{n+i}^2 \equiv 2(2^{2^i}p_iq_n^{2^i})^2-(2^{2^i}q_iq_n^{2^i})^2 =2^{2^{i+1}}q_n^{2^{i+1}}(2p_i^2-q_i^2) =2^{2^{i+1}}p_{i+1}q_n^{2^{i+1}} &\pmod{p_n}\\ q_{n+(i+1)} =2q_{n+i}^2+p_{n+i}^2 \equiv 2(2^{2^i}p_iq_n^{2^i})^2+(2^{2^i}q_iq_n^{2^i})^2 =2^{2^{i+1}}q_n^{2^{i+1}}(2p_i^2+q_i^2) =2^{2^{i+1}}q_{i+1}q_n^{2^{i+1}} &\pmod{p_n}, \end{align*}hence proved. Since we already showed $\gcd(p_k,q_k)=1$ for all $k$, to prove that $\gcd(p_{m+i},q_m)=1$ for any $i \geq 1$, it suffices to show that $\gcd(p_i,q_m)=1$. Likewise, as $p_n$ is always odd, to prove that $\gcd(p_n,q_{n+i})=1$ for any $i \geq 1$, it suffices to show that $\gcd(p_n,q_i)=1$. As such, we can reduce the claim from $(m,n)$ to either $(m-n,n)$ or $(m,n-m)$ (whichever one has two positive terms). This is just the Euclidean Algorithm, so repeating this until we cannot reduces the claim from $(m,n)$ to $(\gcd(m,n),\gcd(m,n))$, which we have already proven holds, so we're done. $\blacksquare$

Direct induction shows that all terms of the sequences are odd. Let $r>2$ be an arbitrary prime and let $n$ be minimal such that $r$ divides at least one of $p_n$ and $q_n$. It is not possible that $r$ divides both $p_n$ and $q_n$, else it would divide $q_{n-1}^2 = \frac{p_{n}+q_{n}}{4}$ and so it divides $q_{n-1}$, contradicting the minimality of $n$. Now suppose $r\mid q_n$, $r\nmid p_n$. Denoting inverses mod $r$ by $^{-1}$, for $x_i = q_ip_i^{-1}$ we have the relation $x_{i+1} = (2q_i^2 + p_i^2)(2q_i^2-p_i^2)^{-1} = (2x_i^2+1)(2x_i^2-1)^{-1}$. Now $x_n \equiv 0 \pmod r$ gives $x_{n+1} \equiv -1 \pmod r$ and $x_{n+2} \equiv 3 \equiv x_2 \pmod r$, so $x_i$ mod $r$ is periodic - thus $p_i^{-1}$ always exists and so $r\nmid p_i$ for all $i$. Finally, suppose $r\nmid q_n$, $r\mid p_n$. For $y_i = q_ip_i^{-1}$ we get $y_{i+1} = (2+y_i^2)(2-y_i^2)^{-1}$ and now $y_n \equiv 0 \pmod r$ gives $y_{n+1} \equiv 1 \equiv y_1 \pmod p$ - so $y_i$ is periodic mod $r$ - thus $p_i^{-1}$ always exists and so $r\nmid p_i$ for all $i$. The result follows.