A partial result. $\textbf{Proposition.}$ If $n\geq 2$ and $n+1$ is a prime number, then $\det(M_n)=-1$. $\textbf{Proof.}$. Note that the entries $M_n[i,j]$ where $j\geq i$ are $0$ except the $M_n[k,k+1]=1$ and $M_n[1,1]=1$. Moreover, the last row of $M_n$ is $0$ except $M_n[n,1]=1$. We calculate all the following determinants by development along the last column; let $N_{n-1}$ be the matrix obtained from $M_n$ by removing the last column and the penultimate row; then $\det(M_n)=-\det(N_{n-1})$. And so on; $\det(N_{n-1})=-\det(N_{n-2})$..... Since $n$ is even, $\det(M_n)=\det(N_2)$ where $N_2=\begin{pmatrix}*&1\\1&0\end{pmatrix}$. $\square$

It's easy to see that if $n+1=a^2b$ ($a>1$), then the $n$-th row and the $(ab-1)$-th row are the same. As noted by loup blanc above, the first $n-1$ rows are independent, and in the case $n+1=p_1\cdots p_k$, where the $p_i$'s are distinct primes, we can use the rows whose index $i$ is s.t. $i+1|n+1$ ($i<n$) to reduce row $n$ to $(\pm1,0,...,0)$, which is independent from the first $n-1$ rows. For instance for $k=3$, the last row has a 1 in columns $1,p_1,p_2,p_3, p_1p_2,p_1p_3,p_2p_3$, 0 otherwise. Subtracting the rows $p_1p_2-1,p_1p_3-1,p_2p_3-1$, we get --2 in column 1, -1 in columns $p_1,p_2,p_3$, 0 otherwise. Adding the rows $p_1-1,p_2-1,p_3-1$ we get 1 in column 1, 0 otherwise. In general, you first subtract to the last row the rows whose index is 1 less than a product of $k-1$ $p_i$'s, then add the rows whose index is 1 less than a product of $k-2$ $p_i$'s, then subtract the rows whose index is 1 less than a product of $k-3$ $p_i$'s and so on. At the end, the last row will be all 0 except for the first entry which is an alternating sum of binomial coefficients except the last, i.e. $\pm1$.

Quick summary of my sol here: Consider the the determinant formula as sum over all permutations of ${1,\ldots, n}$. We split depending on the value of $k=\sigma(n)$ (which must be a divisor of $n+1$). One can show by examining where $n,n-1,\ldots$ are placed, that $\sigma(l)=l+1$ for $k\leq l <n$. Thus we ontain a recursive formula for $det(M(n))$ in terms of $det(M(k-1))$ for $k|n+1$. Let $\alpha_n = (-1)^{n-1} det(M(n-1))$. Then the recursive formula can be written as: $$\sum_{k|n} \alpha_k = 0$$ where the sum is over positive integer divisors. This combined with $\alpha_1 = 1$ defines the Möbius function, so $\alpha_n=\mu(n)$ and $$det(M(n)) = (-1)^n\mu(n+1)$$ So it is clear that $det(M(n))\neq 0$ iff $n+1$ is square-free.