Maximum of a quantity for two normal orthogonal vectors in $\mathbb{R}^n$

Just use Cauchy-Schwarz and the identity $$ \sum_{i,j}(u_iu_j-v_iv_j)^2=\left[\sum_i u_i^2\right]^2+\left[\sum_i v_i^2\right]^2-2\left[\sum_i u_iv_i\right]^2=2 $$ to get $f(u,v)\le \sqrt2 n$ for all $n$. As you have observed yourself, this is sharp for even $n$. For odd $n$ you can, probably, do a bit better but the estimates get messy and it is not clear (to me) what the sharp bound really is.

Numerical approximations suggest $M(n)=\sqrt{2n^2-1}$ when $n$ is odd, with the max reached for some $u=(a,b,a,b,\dots,a)$, $v=(c,d,c,d,\dots,c)$. Solving exactly for such $u,v$ is easy and only implies a quadratic equation in one variable, $x=b^2$ for instance. Assuming $b>d>0$ without loss of generality, one finds $b^2 = \frac{1}{n-1}(1+\frac{n}{\sqrt{2n^2-1}})$ and deduce $a,c,d$ from the constraints $|u|=|v|=1$ and $u\cdot v=0$, yielding $M(n)\ge \sqrt{2n^2-1}$ when $n$ is odd. Now we still must show that more $a$ in $u$ or more than two distinct components in $u$ cannot improve the bound.

EDIT: Here are elementary details on an analysis for $u$ and $v$ restricted to
$$u=(a,a,\dots,a,b,b,\dots,b)\in\{a\}^{k}\times\{b\}^{\ell}$$ $$v=(c,c,\dots,c,d,d,\dots,d)\in\{c\}^{k}\times\{d\}^{\ell}$$ with $k+\ell=n$ odd or even and $0\lt d\le b$ and $0\lt a\le -c$.

$\langle u|u\rangle = \langle v|v\rangle = 1$ and $\langle u|v\rangle = 0$ translate into $$ka^2+\ell b^2 = 1$$ $$kc^2+\ell d^2 = 1$$ $$kac+\ell bd = 0$$ hence $$(kac)^2 = (\ell bd)^2 = (\ell b^2)(\ell d^2) = (1-ka^2)(1-kc^2)$$ simplifies into $$ka^2+kc^2 = 1$$ and likewise $$\ell b^2+\ell d^2 = 1$$ Furthermore $$\begin{matrix} k\ell(ab)^2 &=& (ka^2)(\ell b^2) &=& (1-\ell b^2)(\ell b^2) & &\\ k\ell(cd)^2 &=& (kc^2)(\ell d^2) &=& (1-\ell d^2)(\ell d^2) &=& (\ell b^2)(1-\ell b^2)\\ \end{matrix}$$ hence $0\lt 1-\ell b^2$ and $$ab = -cd = \sqrt{\frac{b^2-\ell b^4}{k}}$$

This all enables to write $$f(u,v) = k^2(c^2-a^2)+\ell^2(b^2-d^2)+2k\ell(ab-cd)$$ $$= k(1-2ka^2)+\ell(2\ell b^2-1)+4k\ell ab$$ $$= k(2\ell b^2-1)+\ell(2\ell b^2-1)+4k\ell ab$$ and finally $$f(u,v) = g(x) := 2n\ell x -n + 4\ell\sqrt{k}\sqrt{x-\ell x^2}$$ where $0\lt x=b^2\lt \frac{1}{\ell}$. Actually $b^2$ cannot be arbitrarily close to $0$ because from our assumptions $$1 = \ell b^2+\ell d^2 \le 2\ell b^2$$ thus $$\frac{1}{2\ell}\le x=b^2\lt \frac{1}{\ell}$$

Now $$g'(x)=2n\ell + 2\ell\sqrt{k}\frac{1-2\ell x}{\sqrt{x-\ell x^2}}$$ starts positive and goes toward $-\infty$ on the mentioned interval for $x$, therefore $g(x)$ and $f(u,v)$ will be maximal when $g'(x)=0$, which happens when $$ 2\ell x-1 = \frac{2n\ell}{2\ell\sqrt{k}}\sqrt{x-\ell x^2}$$ or equivalently on the prescribed interval $$ (2\ell x-1)^2 = \frac{n^2}{k}(x-\ell x^2)$$ which is the quadratic equation $$x^2-\frac{1}{\ell}x+\frac{k}{\ell(4k\ell+n^2)} = 0$$ whose solutions are $$x_\pm = \frac{1}{2\ell} \pm \frac{1}{2}\sqrt{\frac{1}{\ell^2}-\frac{4k}{\ell(4k\ell+n^2)}}$$ $$= \frac{1}{2\ell} \pm \frac{1}{2}\sqrt{\frac{4k\ell+n^2-4k\ell}{\ell^2(4k\ell+n^2)}}$$ $$= \frac{1}{2\ell} \left(1 \pm \frac{n}{\sqrt{4k\ell+n^2}}\right)$$ where only $x_+$ is in $[\frac{1}{2\ell},\frac{1}{\ell})$. The maximum is then $$g(x_+) = \frac{n^2}{\sqrt{4k\ell+n^2}} + 4\ell\sqrt{k}\sqrt{x_+-\ell x_+^2}$$ The constant coefficient in the quadratic equation is also $x_+x_-$ thus $$x_+-\ell x_+^2=x_+(1-\ell x_+)=x_+(\ell x_-)=\ell x_+x_- = \frac{k}{4k\ell+n^2}$$ yields $$g(x_+) = \frac{n^2+4\ell k}{\sqrt{4k\ell+n^2}} = \sqrt{4k\ell+n^2}$$

In the end, when $u$ and $v$ are restricted to the shapes above, $f(u,v)$ is maximal for $$a = +\sqrt{\frac{1}{2k} \left(1 - \frac{n}{\sqrt{4k\ell+n^2}}\right)}\;, \quad b = \sqrt{\frac{1}{2\ell} \left(1 + \frac{n}{\sqrt{4k\ell+n^2}}\right)}\\ c = -\sqrt{\frac{1}{2k} \left(1 + \frac{n}{\sqrt{4k\ell+n^2}}\right)}\;, \quad d = \sqrt{\frac{1}{2\ell} \left(1 - \frac{n}{\sqrt{4k\ell+n^2}}\right)}\\ $$ and the maximum is $$f(u,v)=\sqrt{4k\ell+n^2}$$ Now allowing $k$ and $\ell=n-k$ to vary for $n$ fixed, one gets that $f(u,v)=\sqrt{4k\ell+n^2}$ is maximum over $k$ for $k=n/2$ when $n$ is even, in which case $f(u,v)=\sqrt{2n^2}$, and $k=(n\pm1)/2$ when $n$ is odd, in which case $f(u,v)=\sqrt{2n^2-1}$. We still have to show that other shapes for $u$ and $v$ cannot improve $f(u,v)$.