Let $M(n, m) = |n\sqrt{n^2+1} - m|$. Using an obvious chain of inequalities
$$n^2 < n\sqrt{n^2+1} < n^2 + \frac{1}{2},$$
we obtain
$$n^2 - m < n\sqrt{n^2+1} - m < n^2 - m + \frac{1}{2}.$$
Therefore, if $m \neq n^2$ then $M(n, m) > 1/2$. Since $1/2 > \sqrt{2}-1$, the required inequality is proved for all $m \neq n^2$.

Let $m = n^2$. Consider the function $f(n) = M(n, n^2) = n\sqrt{n^2+1} - n^2$. We will show that it increases at $n > 0$. Indeed, for all $a > b > 0$ the difference $f(a) - f(b)$ can be transformed:
$$\begin{aligned} & (a\sqrt{a^2+1} - a^2) - (b\sqrt{b^2+1} - b^2) = (a\sqrt{a^2+1} - b\sqrt{b^2+1}) - (a^2 - b^2) = \\ & = \frac{a^2(a^2+1) - b^2(b^2+1)}{a\sqrt{a^2+1} + b\sqrt{b^2+1}} - (a^2 - b^2) = (a^2 - b^2)\left(\frac{a^2 + b^2 + 1}{a\sqrt{a^2+1} + b\sqrt{b^2+1}} - 1\right). \end{aligned} \quad (1)$$
As mentioned above, $a^2 + \frac{1}{2} > a\sqrt{a^2+1}$ and $b^2 + \frac{1}{2} > b\sqrt{b^2+1}$. Summing these inequalities and substituting to (1) we obtain that $f(a) - f(b) > 0$.
Therefore, the minimum of the function $f(n)$ is achieved at $n = 1$ and equals $\sqrt{2}-1$.