Divide-and-conquer works. It takes $O(\log n)$ submatrices to partition the $0$s.  So, for large $n$, it takes fewer than $n$ submatrices.

Let $M'_n$ be the same as $M_n$ except with a $0$ in position $(1,n)$. Let $f(n)$ be the minimum number of submatrices required to cover $M'_n$. It takes at most $f(n)+2$ submatrices to cover the $0$s of $M_{n+1}$ since removing the first row and last column of $M_{n+1}$ produces $M'_n$ transposed.

**Claim:** $f(2n+1) \le f(n)+4$.

**Proof:** Use two submatrices to cover the top right quadrant $\{1,..,n\} \times \{n+2,...,2n+1\}$ and the bottom left quadrant $\{n+2,...,2n+1\} \times \{1,...,n\}$, then two more to cover the central row $\{n+1\} \times *$ and the central column $* \times \{n+1\}$.

The remainder is two copies of $M'_n$ that can be covered in parallel. If $S \subset \{1,...,n\}$ then let $S^+$ be $S \cup \{s+n+1|s\in S\}$. If $\{r_i \times c_i\}$  covers $M'_n$ then $\{r_i^+ \times c_i^+\}$ covers the $0$s in the top left and bottom right quadrants of $M'_{2n+1}$.

----

Since $f$ is nondecreasing, $f(2n) \le f(n)+4$, and $f(2^n) \le 4n$.