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

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

There is also a logarithmic lower bound. Let $I_n$ be the $n\times n$ identity matrix. Let $g(n)$ be the size of the minimal cover of the $0$s of $I_n$. Covering the zeros of $M_n$ also covers the zeros of any submatrix, including $\{1,3,5,...\} \times \{1,3,5,...\} = I_{\lceil n/2 \rceil}$ so $f(n) \ge g(\lceil n/2 \rceil)$.

Suppose you have a cover of the $0$s of $I_n$. Any submatrix is of the form $R \times C$ with $R$ and $C$ disjoint, so at least one of $R$ and $C$ has size at most $n/2$. Without loss of generality, let that be $C$. The other submatrices cover the size $n-\#C$ identity submatrix $(\{1,...,n\}\setminus C) \times (\{1,...,n\}\setminus C).$ So, $g(n) \ge 1+g(n-\#C) \ge 1+g(n/2).$ This implies $g(2^n) \ge n, f(2^n) \ge n-1.$ This means there is a logarithmic lower bound on the number of submatrices needed to cover the $0$s of $M_n$.

So, $f(n) = \Theta(\log n).$