The difference is indeed always at most $(n-2)^2$, and combined with an example from the answer by Bill Bradley (the check that the product of his matrices is identity is rather straightforward), this answers to the initial question, if we do not specify the number of 1's in $M$.
Assume that $M$ is a matrix with $k$ 1's, $M^{-1}=E+N$, where $E$ is all-1 matrix, and $N$ has $\ell$ 1's. We should prove that $k+\ell\geqslant 4n-4$. Let $I_0$, $I_1\subset \{1, 2,\dots,n\} $ be the sets of (indices of) rows with even, respectively odd, number of 1's in $M$. Then $[MN]_{i, j}=\delta_{ij}+{\bf 1}(i\in I_1)$. Note that $I_1$ is non-empty as otherwise $M$ would be singular (with all-1 vector in the kernel). Denote $r=|I_1|$.
Assume that we have exactly one 1 in the, say, $s$-th row of $M$, say, $[M]_{s, x}=\delta_{t, x}$ for some $t$ and all $x=1, 2,\dots,n$. Then $[MN]_{s,i}=[N]_{t,i}$ for all $i=1, 2,\dots,n$. Thus, as $s\in I_1$, the $t$-th row of $N$ contains $n-1$ 1's, and for different $s$ we have different $t$'s. If $j\geqslant 1$ is the number of rows of $M$ with exactly one 1, we get that the total number of 1s in $M$ and $N$ is not less then $j\cdot1+j\cdot (n-1)+(n-j)\cdot 2+(n-j-1)\cdot 1=3n-1+j\cdot (n-3)\geqslant 3n-1+n-3=4n-4$ as needed (we used that $M$ is non-singular, thus every row of $M$ contains at least one 1, and $E+N$ is non-singular, thus at most one row of $E+N$ may be all-1, equivalently, at most one row of $N$ may be all-0.)
So, further we may assume that every row of $M$ contains at least two 1's, and also every column of $M$ contains at least two 1's (as the question is invariant under replacement of $M$ to the transpose of $M$).
Assume that we have exactly one 1 in the, say, $s$-th column of $N$: $[N]_{x, s}=\delta_{x, t}$ for some $t=t_s$ and all $x=1, 2,\dots,n$. Then $[MN]_{i,s}=[M]_{i,t}$ for all $i=1, 2,\dots,n$. It means that the $t_s$-th column of $M$ is the same as the $s$-th column of $MN$.
Note that since $M$ is invertible, for the basic vector, say, $e_j$ we get $Ne_j=0 \Leftrightarrow (MN)e_j=0$. This is impossible if $|I_1|>1$, and happens for exactly one index $j$ if $|I_1|=1$. Now consider several cases.
$|I_1|\geqslant 4$. Then the $s$-th column of $N$ and the $t_s$-th column of $M$ contain together at least $4$ 1's. Other columns of $M$ contain at least two 1's, and so do other columns of $N$, totally at least $4n$ 1's in $M$ and $N$.
$|I_1|=3$. The difference with the previous case is that there can be three values of $s$ for which the $s$-th column of $N$ and the $t_s$-th column of $M$ contain together at least three 1's (not at least four). We still get at least $4n-3$ 1's in $M$ and $N$.
$|I_1|=2$. The difference with the first case is that there can be two values of $s$ for which the $s$-th column of $N$ and the $t_s$-th column of $M$ contain together at least two 1's. We still get at least $4n-4$ 1's in $M$ and $N$.
$|I_1|=1$. Let $I_1=\{n\}$, we may suppose this without loss of generality. Then $Ne_n=0$. If there are $\theta$ columns of $N$ with exactly one 1, they correspond to $\theta$ columns of $M$ which are the same as $\theta$ distinct columns of $N$. In particular, the $n$-th row of $M$ contains at least $\theta$ 1's, so totally we get at least $\theta+(n-1)2+\theta\cdot 1+(n-1-\theta)\cdot 2=4n-4$ 1's in $M$ and $N$. (We counted 1's in $M$ by rows and in $N$ by columns).