Solution:

We will generalize the claim. To do this, we allow the $m \times n$ rectangle to be colored on both sides, and allow some of the unit squares to be transparent. Such fields need only be colored on one side and then look the same on both sides. A non-transparent unit square, on the other hand, must be colored on both sides, though not necessarily with the same color.

Now let $A$ be the number of all such colorings of the top side for which there exists at least one black path from the left edge to the right edge of the rectangle. Correspondingly, let $B$ be defined for the bottom side. Furthermore, let $C$ be the number of all colorings for which there exist two black paths from the left edge to the right edge of the rectangle, namely one on the top side and one on the bottom side, which do not contain a common transparent square. Finally, let $D$ be the number of all colorings of this rectangle. We will prove (I) $A \cdot B \geq C \cdot D$ and thereby have shown the original claim as the special case in which all fields are transparent. In that case, we have $A=B=N, C=M, D=2^{m n}$.

We carry out the proof of (I) by induction on the number $k$ of transparent fields. For $k=0$ we have $A=B=N \cdot 2^{m n}, C=N^{2}$ and $D=\left(2^{m n}\right)^{2}$, so that equality holds in (I). Now assume that the claim holds for $k$, and consider a rectangle with $k+1$ transparent fields. The numbers $A, B, C, D$ now refer to this rectangle. We choose a transparent unit square $t$ and make it opaque. For the rectangle thus obtained, let the respective numbers be denoted by $A^{\prime}, B^{\prime}, C^{\prime}, D^{\prime}$, and by the induction hypothesis we have $A^{\prime} \cdot B^{\prime} \geq C^{\prime \prime} \cdot D^{\prime}$.

Now obviously $D^{\prime}=2 \cdot D$. For every coloring counted in $A$, there exist exactly two colorings counted in $A^{\prime}$, namely distinguished by whether $t$ is colored black or white on its underside. Conversely, to two colorings counted in $A^{\prime}$ that differ only in the color of the underside of a square, one can assign a single coloring counted in $A$. Hence $A^{\prime}=2 \cdot A$ and likewise $B^{\prime}=2 \cdot B$. To prove (I) for $k+1$, it therefore suffices to show $C^{\prime} \geq 2 \cdot C$.

For this, let $t$ again be transparent. Since $C$ only counts those colorings that contain at least one black path on top and one on the bottom, where these do not intersect in a transparent square, $t$ can lie on at most one of these paths, say without loss of generality on the top one. So if we make $t$ opaque and keep its color on top, we can color its underside black or white, and both colorings are counted in $C^{\prime}$. In doing so, different colorings counted in $C$ always yield different pairs of colorings counted in $C^{\prime}$. This proves everything.