Small integral representation as $x^2-2y^2$ in Pell's equation Let $k$ be a "representable" positive integer, in the sense
that $k=|x^2-2y^2|$ for some integers $x,y$. Does it necessarily
follow that $k$ can also be represented with small parameters,
i.e. $k=|u^2-2v^2|$ with $|u|\leq\sqrt{k},|v|\leq\sqrt{k}$ ?
My (mostly useless) thoughts : if $N$ is very big and $a_N,b_N$
are the unique integers such that $a_N+b_N\sqrt{2}=(\sqrt{2}-1)^N(x+y\sqrt{2})$,
then $|a_N+b_N\sqrt{2}|$ can be arbitrarily small, but unfortunately
that doesn't make the individual $a_N$ and $b_N$ small.
Also, we know that $k$ is representable iff all the prime divisors of
$k$ are such that $2$ is a quadratic residue to them, but that doesn't seem
to help either.
 A: Appendix 1: all pairs $(u,v)$ in the tree depicted satisfy $u \geq 2v.$ As a result, 
$$ k = u^2 - 2 v^2 \geq 4 v^2 - 2v^2 = 2 v^2,  $$
so $$2 v^2 \leq k$$
and $$ \color{blue}{ v \leq \sqrt {\frac{k}{2}}}. $$ 
Appendix 2:
we may demand
$$ v \leq \frac{u}{2}. $$
Therefore
$$  2 v^2 \leq \frac{u^2}{2}, $$
$$  -2 v^2 \geq - \frac{u^2}{2}, $$
$$ k = u^2 -2 v^2 \geq u^2 - \frac{u^2}{2} =  \frac{u^2}{2}, $$
$$ u^2 \leq 2 k,  $$
$$ \color{blue}{ u \leq \sqrt {2k}}. $$
preliminary: I already think you are roughly correct. The Conway topograph method deals most directly with $u+v$ when both are positive. The largest variables come from
$$ u = 2n + 1, \; \; v = n, \; \;  u^2 - 2 v^2 = 2 n^2 + 4 n + 1  $$ 
Note that this "branch" of the tree illustrates both inequalities well, $  u \leq \sqrt {2k} $ and $  v \leq \sqrt {\frac{k}{2}}. $
I have answered several questions with these diagrams, also the book describing the method is at CONWAY.  The point is that any (positive) number represented occurs in the first tree on the positive side of the river:


Just noticed the absolute values in the original question. If you are willing to represent $-k$ instead of $k,$ you get the bounds you wanted. This happens in an upside-down tree below the river where we have $u^2 - 2 v^2 = -k$ for positive $k,$ and with $u,v > 0$ and $v \geq u.$ Similar arguments to the above give your desired bounds, 
$$  u \leq \sqrt k, \; \; \;  v \leq \sqrt k. $$

