This is basically a polynomial Pell's equation. Therefore let us work in $R=\mathbb{R}[x][\sqrt{x^2+1}]$ (which if we want is isomorphic to $\mathbb{R}[x,y]/(x^2+1-y^2)$ ). We see that if $f=P+\sqrt{x^2+1}Q\in R$ then $N(f)=P^2-(x^2+1)Q^2$ is a multiplicative function. The equation then is $N(f)=-1$. We see that $f=x+\sqrt{x^2+1}$ satisfies $N(f)=-1$, and therefore $g=f^2=2x^2+1+\sqrt{x^2+1}2x$ satisfies $N(g)=1$. Now assume there is a solution with degree greater than or equal to $2$. If so we can write it as $F=P+\sqrt{x^2+1}Q=(Ax^n+Bx^{n-1}+Cx^{n-2}+O(x^{n-3}))+\sqrt{x^2+1}(Dx^{n-1}+Ex^{n-2}+Fx^{n-3}+O(x^{n-4}))$, where wlog $A,D>0$. Equating the higher coefficients in $N(F)=-1$, we get $-1=(A^2-D^2)x^{2n}+(2AB-2DE)x^{2n-1}+(2AC+B^2-2DF-E^2-D^2)x^{2n-2}+O(x^{2n-3})$ This implies $A^2=D^2\implies A=D$, $2AB=2DE\implies B=E$, $2AC+B^2-2DF-E^2-D^2=0\implies 2AC-2AF-A^2=0\implies 2C-2F-A=0$. Now consider the element $\tilde Fg^{-1}=F((2x^2+1)-\sqrt{x^2+1}2x)$ By multiplicativity, we have $N(\tilde{F})=-1$, but we also have $deg(\tilde(F))=deg(F)-2<deg(F)$. So by induction we must have $F=g^nh$ where $deg h<2$ and $N(h)=-1$. Setting $h(x)=ax+b+c\sqrt{x^2+1}$, we get the equations $a^2-c^2=0$, $2ab=0$ and $b^2-c^2=-1$. If $a=c=0$ we have a contradiction, so assume wlog $a=c>0$. So we have $2ab=0\implies b=0\implies -c^2=-1\implies c=1$. So the only solutions for $h$ are $h(x)=x+\sqrt{x^2+1}$, together with the other choices of signs. Therefore we always have $deg(F)=deg(g^nh)=ndeg(g)+deg(h)=2n+1$, and thus the degree can only be odd. Conversely, taking $P+\sqrt{x^2+1}Q=g^nh$, yields all odd numbers.

A key idea when solving $A^2 - DB^2 = 1$ in integers for a fixed non-perfect square $D$, without the need to remember any formulae, is as follows: find by hand a small-ish solution $(A_0, B_0)$ and then find positive constants $a$, $b$, $c$, $d$ such that if $(A,B)$ is a solution, then so is $(aA + bB, cA + dB)$ (by opening the brackets, nothing more). Let's sketch that here (but with $a$, $b$, $c$, $d$ being polynomials), it will solve the problem completely! Observe that $P(x) = x$, $Q(x) = 1$ is a solution and that if $(P, Q)$ is a solution, then $\deg P = \deg Q + 1$. Now the key point is that if $(P,Q)$ is a solution, then so are $((2x^2+1)P + 2x(x^2+1)Q, 2xP + (2x^2+1)Q)$ and $((2x^2+1)P - 2x(x^2+1)Q, -2xP + (2x^2+1)Q)$. From the first pair we inductively see that all odd $\deg P$ are possible (each time the degrees of $P$ and $Q$ increase by $2$) and from the second pair we see that if $\deg P$ is even, then we will have a solution with $\deg P = 2$, $\deg Q = 1$ - by expanding we see that this is impossible. (Perhaps it could also be possible to avoid expanding, by somehow saying that if $\deg P = 2$, $\deg Q = 1$ was possible, then so would have been $\deg P = 0$ and $Q \equiv 0$ or something like that, but for safety I would prefer to do the bashing, it's not long.)

Assassino9931 wrote: from the second pair we see that if $\deg P$ is even, then we will have a solution with $\deg P = 2$, $\deg Q = 1$ - by expanding we see that this is impossible. (Perhaps it could also be possible to avoid expanding, by somehow saying that if $\deg P = 2$, $\deg Q = 1$ was possible, then so would have been $\deg P = 0$ and $Q \equiv 0$ or something like that, but for safety I would prefer to do the bashing, it's not long.) Not my idea but this idea is useful for that part as well: Assume there is a real root of $Q$. Plugging into the original equation we have $-1$ equal to the square of a real number which is impossible. Hence the degree of $Q$ cannot be odd.

@above Awesome, I somehow tried this but no idea why I did not see it work, I like it even more than what I wrote!

$P(x)=\pm \frac{1}{2} \left ( \left ( \sqrt{x^2+1}+x \right )^d - \left ( \sqrt{x^2+1}-x \right )^d\right )$ and $Q(x)=\frac{1}{d}P'(x)=\pm \frac{1}{2} \frac{1}{\sqrt{x^2+1}} \left ( \left ( \sqrt{x^2+1}+x \right )^d + \left ( \sqrt{x^2+1}-x \right )^d\right )$ so $d$ will be all odd numbers.

Assassino9931 wrote: A key idea when solving $A^2 - DB^2 = 1$ in integers for a fixed non-perfect square $D$, without the need to remember any formulae, is as follows: find by hand a small-ish solution $(A_0, B_0)$ and then find positive constants $a$, $b$, $c$, $d$ such that if $(A,B)$ is a solution, then so is $(aA + bB, cA + dB)$ (by opening the brackets, nothing more). Let's sketch that here (but with $a$, $b$, $c$, $d$ being polynomials), it will solve the problem completely! Observe that $P(x) = x$, $Q(x) = 1$ is a solution and that if $(P, Q)$ is a solution, then $\deg P = \deg Q + 1$. Now the key point is that if $(P,Q)$ is a solution, then so are $((2x^2+1)P + 2x(x^2+1)Q, 2xP + (2x^2+1)Q)$ and $((2x^2+1)P - 2x(x^2+1)Q, -2xP + (2x^2+1)Q)$. From the first pair we inductively see that all odd $\deg P$ are possible (each time the degrees of $P$ and $Q$ increase by $2$) and from the second pair we see that if $\deg P$ is even, then we will have a solution with $\deg P = 2$, $\deg Q = 1$ - by expanding we see that this is impossible. (Perhaps it could also be possible to avoid expanding, by somehow saying that if $\deg P = 2$, $\deg Q = 1$ was possible, then so would have been $\deg P = 0$ and $Q \equiv 0$ or something like that, but for safety I would prefer to do the bashing, it's not long.) Let me now write this down properly. Comparing degrees shows that $\deg Q = d-1$. Suppose firstly that $d$ is even. Then $d-1$ is odd, so $Q$ has a real root $x_0$, but then $P(x_0)^2 + 1 = 0$, which is impossible, as the left-hand side is positive. Now we show that all odd $d$ work. Note that $P(x) = x$, $Q(x) = 1$ is a solution. Aim: find non-constant polynomials $A,B,C,D$ such that if $(P, Q)$ is a solution with, then so is $(AP+BQ, CP+DQ)$. We want \[ (AP + BQ)^2 - (x^2+1)(CP + DQ)^2 = -1 = P^2 - (x^2+1)Q^2 \]\[ \left[A^2 - (x^2+1)C^2\right]P^2 + 2\left[AB - (x^2+1)CD\right]PQ + \left[B^2 - (x^2+1)D^2\right]Q^2 = P^2 - (x^2+1)Q^2 \]which is equivalent to $A^2 - (x^2 + 1)C^2 = 1$, $AB = (x^2+1)CD$, $B^2 - (x^2+1)D^2 = -(x^2+1)$. A constant $C$ does not fit, but trying linear $C$ shows that $C(x) = 2x$ works, with $A = 2x^2 + 1$. The equation for $B$ and $D$ shows that $B$ must be divisible by $x^2+1$ and now it is easy to guess that $B = 2x(x^2+1)$, $D = A = 2x^2 + 1$ works. Hence if $(P,Q)$ is a solution to the equation with positive leading coefficients, so is \[((2x^2+1)P + 2x(x^2+1)Q, 2xP + (2x^2+1)Q).\]Each time the degrees of $P$ and $Q$ increase by $2$ in the new generated solution, so all odd $d$ are possible, as desired.