I am trying to get the following into a nice expression in terms of $n$ by using inequalities.
$$\sup_{x \in [-1,1]}\left| \sqrt{x^2+\frac1n \cos^2(nx)} - |x| \right| \leq \sup_{x \in [-1,1]}\left| \sqrt{x^2+\frac1n} - |x| \right|$$
and now I am stuck as to what to do next!
By symmetry the last expression equals $$\sup_{x \in [0,1]} \left( \sqrt{ x^2 + \frac 1n} - x\right).$$ Let $\phi(x) = \sqrt{x^2 + 1/n} - x$. Then $$\phi'(x) = \frac{x}{\sqrt{x^2 + \frac 1n}}- 1 < 0$$ because $\sqrt{x^2 + \frac 1n} > x$ for all $x$. Thus $\phi$ is decreasing on $[0,1]$ so its supremum on this interval is attained at $x=0$. It follows that$$\sup_{x \in [0,1]} \left( \sqrt{ x^2 + \frac 1n} - x\right) = \frac{1}{\sqrt n}.$$
Alternatively, for all $x \ge 0$ you have $$\sqrt{x^2 + \frac 1n} - x = \frac{x^2 + \frac 1n - x^2}{\sqrt{x^2 + \frac 1n} + x} = \frac{\frac 1n}{\sqrt{x^2 + \frac 1n} + x} \le \frac{\frac 1n}{\frac 1{\sqrt n}} = \frac{1}{\sqrt n}.$$