This is only a partial answer. But maybe it will be helpful to someone.
$(1)$ I was only able to show that $M_n\leq p$, where $p$ is the first prime larger than $n^2!n$.
$(2)$ For the existence of $n^2$ numbers $a_1, \ldots, a_{n^2}\in [a,b]$ such that every matrix whose entries form a permutation of the set $\{a_1, \ldots, a_{n^2}\}$ has a nonzero determinant, it is necessary and sufficient that $a<b$ (one can even guarantee that in this case, the numbers can be chosen to be rationals).
Let's see why $(2)$ is true first, because it is related to my answer to $(1)$. We will use methods from algebraic geometry.
Clearly, $a<b$ is a necessary condition, and we only need to show that it is sufficient. Let $K$ be an infinite field. Denote by $f(X_1,\ldots, X_{n^2})$ the polynomial $\mathrm{det}(X_1,\ldots, X_{n^2})\in K[X_1,\ldots, X_{n^2}]$. Because the identity matrix has a determinant $1$, the vanishing subset $V(f):=\{(c_1,\ldots, c_{n^2})\in K^{n^2}\mid f(c_1,\ldots, c_{n^2})=0\}$ of $f$ in $K^{n^2}$ is not the whole $K^{n^2}$. By the same reasoning, for any permutation $\sigma\in S_{n^2}$ (where $S_{n^2}$ is the group of all permutations on the set $\{X_1,X_2,\ldots, X_{n^2}\}$), define $\sigma(f)$ to be the polynomial $\det(\sigma(X_1),\ldots, \sigma(X_{n^2}))$, then $V(\sigma(f))$ is also a proper subset of $K^{n^2}$. But we know that $K^{n^2}$ as an affine variety is irreducible, which means that it is not a finite union of proper closed subsets, thus $\bigcup_{\sigma \in S_{n^2}} V(\sigma(f))$ is a proper subset of $K^{n^2}$. This means that on any infinite field $K$, one can always choose $n^2$ elements $a_1, \ldots, a_{n^2}$ such that any matrix whose entries form a permutation of the $n^2$ elements has a non-zero determinant.
Now let $K=\mathbb{R}^{n^2}$. Then every proper Zariski-closed subset of $\mathbb{R}^{n^2}$ is nowhere dense, implying that the complement of a proper Zariski-closed subset is a dense open subset of $\mathbb{R}^{n^2}$ in the Euclidean sense. Thus, if $a<b$, then $[a,b]^{n^2}$ contains at least a point which is an interior point (in the Euclidean sense) of the complement of $\bigcup_{\sigma\in S_{n^2}}V(\sigma(f))$; in particular, there is a point with rational coordinates in the complement of $\bigcup_{\sigma\in S_{n^2}}V(\sigma(f))$. This shows that $(2)$ is true.
Coming back to $(1)$. To find such $n^2$ numbers $a_1,\ldots, a_{n^2}$ in $\mathbb{N}_{+}$, it is sufficient to find $n^2$ elements $b_1, \ldots, b_{n^2}$ in $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ for some prime number $p$, where some of the $b_i$ are allowed to be zero, but when lifting the zero elements back to $\mathbb{Z}$, we use $p$ instead. However, this won't give you a sharp upper bound (i.e. the existence of $a_1,\ldots, a_{n^2}$ does not guarantee the existence of $b_1, \ldots, b_{n^2}$). Let $K=\mathbb{F}_p$. Since $\mathbb{F}_p$ is a finite field, $\mathbb{F}_p^{n^2}$ is not longer irreducible, the above method does not work. But it is still true that $\bigcup_{\sigma \in S_{n^2}}V(\sigma(f))$ is not the whole $K^{n^2}$ as long as $p>n^2!n$. To see this, let's calculate the number of points in $V(f)$, to do this, we use the classical result that
$$ \left| \mathrm{GL}_n(\mathbb{F}_p)\right| = (p^n-1)(p^n-p)\cdot \cdots \cdot (p^n-p^{n-1}).$$
We see that
$$ |V(f)| = p^{n^2} - \left| \mathrm{GL}_n(\mathbb{F}_p)\right|=p^{n^2}-(p^n-1)(p^n-p)\cdot \cdots \cdot (p^n-p^{n-1}).$$
So
$$
\begin{align}
\left|\bigcup_{\sigma\in S_n}V(\sigma(f))\right| &\leq n^2!\left[p^{n^2}-(p^n-1)(p^n-p)\cdot \cdots \cdot (p^n-p^{n-1})\right] \\
&<n^2!\left[p^{n^2}-(p^n-p^{n-1})^n\right] \\
&=p^{n^2}n^2!\left[1-\left(1-\frac{1}{p}\right)^n\right] \\
&=p^{n^2}n^2!\sum_{k=1}^n{n\choose k}(-1)^{k-1}\frac{1}{p^k}. \tag{A}
\end{align}
$$
Notice that when $p>n^2!n$, for any $k$ such that $1\leq k< n$, we have
$$ p> n-k> \frac{n-k}{k+1} =\frac{\frac{n!}{(k+1)!(n-k-1)!}}{\frac{n!}{k!(n-k)!}}= \frac{n \choose k+1}{n\choose k},$$
so
$$ {n\choose k} \frac{1}{p^k} > { n\choose k+1} \frac{1}{p^{k+1}}. $$
This means (think about the alternating series) in Inequality $(A)$ we have
$$ \sum_{k=1}^n {n\choose k}(-1)^{k-1}\frac{1}{p^k} \leq {n\choose 1} \frac{1}{p} =\frac{n}{p}.$$
Thus,
$$\left|\bigcup_{\sigma\in S_{n^2}}V(\sigma(f))\right| < p^{n^2}\frac{n^2!n}{p}< p^{n^2}.$$
In conclusion, $(1)$ is also true.
