What is the asymptotic expansion of $x_n$ where $x_{n+1} = x_n+1/x_n$?

Not a complete answer. Let me first reproduce what I imagine is your argument. We have $y_{n+1} = y_n + \frac{1}{y_n} + 2$. In particular $y_{n+1} \ge y_n + 2$ which gives $y_n \ge 2n + a^2$ and hence $\frac{1}{y_n} \le \frac{1}{2n + a^2}$. This gives

$$y_{n+1} \le y_n + 2 + \frac{1}{2n + a^2}$$

which gives

$$y_n \le 2n + \sum_{i=0}^{n-1} \frac{1}{2i + a^2} + a^2 = 2n + \frac{1}{2} \log n + C$$

for some constant $C$. Write $y_n = 2n + \frac{1}{2} H_{n-1} + e_n$, where we now know that $e_n$ is bounded from above by a constant (and it's not hard to show that it's bounded from below by a constant also). Then the recurrence relation gives

$$y_{n+1} - y_n = 2 + \frac{1}{2n} + e_{n+1} - e_n = \frac{1}{2n + \frac{1}{2} H_{n-1} + e_n} + 2$$

and rearranging a bit gives

$$e_n - e_{n+1} = \frac{1}{2n} - \frac{1}{2n + \frac{1}{2} H_{n-1} + e_n} = \frac{ \frac{1}{2} H_{n-1} + e_n}{2n \left( 2n + \frac{1}{2} H_{n-1}+ e_n) \right)}.$$

Heuristically this gives something like $e_n = C + \frac{\ln n}{8n} + \dots$ but I don't know how to prove it off the top of my head, mostly because I can't think of a reasonable way to describe the constant $C$.

Not a rigorous answer, and it is rather a continuation of Mr Cohen's work.

My idea
My idea is standard, I just try to put all the approximate terms aside to see what will be left.

Main work
We start by giving the following equation.

$y_{n+1}-2(n+1)-\frac{1}{2}\ln(n+1) = -\frac{\ln(n)}{4ny_n}+\frac{\frac{1}{2}\ln(n) +2n-y_n}{2ny_{n}}-\frac{1}{2}\left[ \ln(1+\frac{1}{n}) -\frac{1}{n}\right]+( y_{n}-2n-\frac{1}{2}\ln(n))$
So if the approximation given by Mr Cohen is true, we have: $$|e_{n+1}-e_n|=\left| -\frac{\ln(n)}{4ny_n}+\frac{\frac{1}{2}\ln(n) +2n-y_n}{2ny_{n}}-\frac{1}{2}\left[ \ln(1+\frac{1}{n}) -\frac{1}{n}\right]\right| \le c_1\frac{ln(n)}{n^2} $$ for some constant $c_1>0$, where $e_n:= y_n-2n-\frac{1}{2}\ln(n)$ as in the post of Mr Qiaochu.
Hence, $e_{n}$ converges to some limit, noted by $C$ also as in the post of Mr Qiaochu

Let $u_n:=e_n-C$ then, the very fist equation is equivalent to $$u_{n+1}-u_n= \frac{-u_n}{2ny_n}-\frac{\ln(n)}{4ny_n}-\frac{C}{2ny_n}-\frac{1}{2}\left[ \ln(1+\frac{1}{n})-\frac{1}{n} \right]$$ Thus, $$-u_N = \sum_{n \ge N}\left\{ \frac{-u_n}{2ny_n}-\frac{\ln(n)}{4ny_n}-\frac{C}{2ny_n}-\frac{1}{2}\left[ \ln(1+\frac{1}{n})-\frac{1}{n} \right] \right\}$$

Clearly, $$ \lim_{N \rightarrow +\infty} \frac{N}{\ln(N)}\sum_{n \ge N}\frac{-u_n}{2ny_n}=0$$ $$\lim_{N \rightarrow +\infty} \frac{N}{\ln(N)}\sum_{n \ge N}\frac{C}{2ny_n}=0$$ $$\lim_{N \rightarrow +\infty} \frac{N}{\ln(N)}\sum_{n \ge N}\left[ \ln(1+\frac{1}{n})-\frac{1}{n}\right]=0$$

And though it is not really straightforward, it is also not hard to see that: $$\lim_{N \rightarrow +\infty} \frac{N}{\ln(N)}\sum_{n \ge N}\frac{\ln(n)}{4ny_n} = \dfrac{1}{8}$$

So, in conclusion $$y_n= 2n+\frac{1}{2}\ln(n)+C+\frac{1}{8}\frac{\ln(n)}{n}+o(\frac{\ln(n)}{n}) $$

Comment: It looks like the next terms are $\frac{1}{n}$ something and $\frac{\ln(n)^2}{n^2}$ something. So, it would be a surprise to me if one can find an analytic form for this series.

Updated comment So, $$x_n=\sqrt{2n}\sqrt{ 1+\frac{y_n-2n}{2n}}= \sqrt{2n}\left[1+\frac{\ln(n)}{8n}+\frac{C}{4n}+\frac{\ln(n)}{32n^2}-\frac{1}{8}\left( \frac{\ln n}{4n}+\frac{C}{2n} \right)^2 +o(\frac{\ln(n)}{n^2}) \right]$$