The bounds...
We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the same paper.
...cannot be substantially improved
There can be a subexponential gap between $Cov(M)+Cov(N)$ and $NFA(L)$. The following example, and the proof of the gap, is an adaptation of a similar example illustrating the limitations of 2-party protocols for proving lower bounds on nondeterministic state complexity from (Hromkovič et al. 2009):
We use the alphabet $[n]= \{\,1,2,\ldots,n\,\}$. Let $L=\{\,xyz\in [n]^3 \mid x=y \vee x\neq z \,\}$.
We first take care of $Cov(M)$. Observe that if $w=xyz$ with $y=z$, then
$w \in L$: in case $x=y$, $w\in L$ and in case $x\neq y$, we also have
$x\neq z$ and thus $w\in L$. Also, if $w$ is of the form $xyz$ with
$y\neq z$, then $w\in L$ iff $x\neq z$. So we can write $L = L'\cup L''$,
with $L'=\{xyz\in [n]^3 \mid y=z\}$ and $L''=\{\,xyz\in [n]^3 \mid y\neq z
\wedge x \neq z \,\}$.
Now consider the bipartite graphs $G' = (U',V',E')$ with $U'=[n]$, $V'=
\{yz \in [n]^2 \mid y=z\}$, $E' = U' \times V'$, as well
as $G'' = (U'',V'',E'')$ with $U''=[n]$, $V''= \{ yz \in [n]^2 \mid
y\neq z\}$,
$E'' = \{(x,yz) \mid x\neq z\}$, and $G = (U' \cup U'',V' \cup V'', E'\cup E'')$.
Then a biclique edge cover for the graph
$G$ gives rise to a covering of $M$ with $1$-monochromatic
submatrices, and vice versa (Theorem 21 in Gruber & Holzer 2006).
A simple kernelization trick for computing a biclique edge cover for $G'$
is to put the twin vertices from $U'$ into equivalence classes. Then we do the same in the resulting graph for the twin vertices from $V'$.
Twin vertices are those with identical neighborhood.
This step does not alter the minimum number of bicliques needed to cover all
edges in the respective graph.
The kernelization step collapses $G'$ into a graph with two vertices and
a single edge. Thus, the edges of $G'$ can be covered with a single
biclique. Applying the kernelization step to $G''$ yields a crown graph
on $2n$ vertices, whose bipartite dimension (the minimum biclique edge
cover number) is known to be $\sigma(n)$, where $\sigma$ is the inverse
function of the middle binomial coefficient (De Caen et al. 1981). Notice that $\sigma(n)=O(\log n)$.
Thus the bipartite dimension of $G$ is $1+\sigma(n)$, which is identical
to $Cov(M)$.
Now consider $Cov(N)$. Observe that if $w=xyz$ with $x=y$, then $w \in
L$. If $x\neq y$, then $x\in L$ iff $x\neq z$. So we can write $L = L'''
\cup L''''$
with $L'''=\{xyz\in [n]^3 \mid x=y\}$ and $L''''= \{xyz\in [n]^3 \mid
x\neq y \wedge x\neq z\}$. Almost the same argument as above yields
$Cov(N)=1+\sigma(n)$.
It remains to give a lower bound on the nondeterministic state
complexity of $L$. Observe that $L$ contains all words of the form $xxx$
with $x\in[n]$. For each such word $xxx$ fix an accepting computation of a minimal
NFA accepting $L$. Let $p_x$ denote the state reached after reading the
prefix $x$, and let $q_x$ denote the state reached after reading the
prefix $xx$ of the input word $xxx$. Then all pairs $(p_x,q_x)$ must be
different. For the sake of contradiction, assume $(p_x,q_x)=(p_y,q_y)$
for some $x\neq y$. Then we can construct an accepting computation
on input $xyx$, such that the NFA is in state $p_x=q_x$ after reading
the prefix $x$, and in state $q_y=q_x$ after reading the prefix $xy$.
But the string $xyx$ is not in $L$. For the state set $Q$ of the NFA, this shows
that $|Q|^2 \ge n$. Thus,
for large $n$, we obtain a subexponential separation between $Cov(M)+Cov(N)$ and $|Q|$ (the nondeterministic state complexity of $L$).
References
Dominique de Caen, David A. Gregory, Norman J. Pullman: The Boolean rank of zero-one matrices, in: Cadogan, Charles C. (ed.), 3rd Caribbean Conference on Combinatorics and Computing, Department of Mathematics, University of the West Indies, pp. 169–173 (1981)
Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity is Hard. Report TR06-027, Electronic Colloquium on Computational Complexity (ECCC), March 2006. Short version appeared in: Oscar H. Ibarra and Zhe Dang, editors, 10th International Conference on Developments in Language Theory (DLT 2006), Santa Barbara (CA), USA, volume 4036 of LNCS, pages 363-374. Springer, June 2006.
Juraj Hromkovic, Holger Petersen, Georg Schnitger: On the limits of the
communication complexity technique for proving lower bounds on the size
of minimal NFAs. Theor. Comput. Sci. 410(30–32): 2972–2981 (2009)
