Split the table into four smaller tables of size $n \times n$. The upper left quarter is now filled with $1$s, the lower right quarter with $-1$s, and each of the remaining two quarters in a checkerboard pattern (if $n$ is odd, fill them in such a way that one of the quarters contains more $1$s than $-1$s, and the other more $-1$s than $1$s). If $n$ is even, then each of the rows and columns contains either $n/2$ $1$s and $3n/2$ $-1$s, or vice versa, so that $M = n$. If $n$ is odd, then each of the rows and columns contains either $(n - 1)/2$ $1$s ($-1$s) and $(3n + 1)/2$ $-1$s ($1$s), or $(n + 1)/2$ $1$s ($-1$s) and $(3n - 1)/2$ $-1$s ($1$s); it follows that $M = n - 1$ in this case.

Now we show that $M$ cannot be larger. If there is a row or column that contains as many $1$s as $-1$s, then $M = 0$, and we are done. Otherwise, split the set of all $4n$ rows and columns into two subsets: those that contain more $1$s than $-1$s, and those that contain more $-1$s than $1$s.

One of these two sets must contain at least $2n$ elements. Without loss of generality, assume that there are at least $2n$ rows and columns (of which $k$ are rows and $\ell$ columns) that contain more $1$s than $-1$s. In each of these rows and columns, there are at least $n + M/2$ $1$s and at most $n - M/2$ $-1$s. The total number of $1$s in all these rows and columns is therefore at least
$$(k + \ell) \left( n + \frac{M}{2} \right) - k\ell,$$
where the last term accounts for those $1$s that are possibly double-counted. Hence we have
$$2n^2 \ge (k+\ell) \left(n + \frac{M}{2}\right) - k\ell \ge (k+\ell) \left(n + \frac{M}{2}\right) - \frac{1}{4}(k+\ell)^2$$
and thus, with $r = k + \ell$,
$$M \le \frac{2n^2 + r^2/4 - rn}{r/2} = \frac{4n^2}{r} + \frac{r}{2} - 2n = n - \frac{(r-2n)(4n-r)}{2r} \le n,$$
since $2n \le r \le 4n$ by assumption. Hence we have $M \le n$, which completes the proof in the case that $n$ is even. If $n$ is odd, $M = n$ is impossible, since all row sums and all column sums must be even (sum of an even number of odd numbers), so that we must have $M \le n - 1$.

We conclude that the largest possible value of $M$ is $n$ if $n$ is even and $n - 1$ if $n$ is odd.