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

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

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