The difference is indeed always at most $(n-2)^2$.

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|$. The rank of $MN$ is always at least $n-1$, and it equals $n$ iff $r$ is even (I omit the direct check of this that may be done by studying the kernel of $MN$). In particular, ${\rm rank}\, N\geqslant {\rm rank}\, MN\geqslant n-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 rows 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 full rank, thus every row of $M$ contains at least one 1, and $N$ has rank at least $n-1$, thus 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 (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.

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

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

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

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