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)$.
