Lemma (Lupanov 1956): Every boolean $n\times m$ matrix $A$ with $\log n\ll m\leq n$ has a decomposition of weight at most $(1+o(1))nm/\log n$. The number of rectangles in this decomposition is $O(nm/\log^3 n)$.Proof: Take a positive integer $q$, and split $A$ column-wise into $\ell\leq m/q$ submatrices $B_1,\ldots,B_{\ell}$ of dimension $n\times q$; the last submatrix may have fewer than $q$ columns. Let $B$ be any of these submatrices.
Claim: $B$ has a decomposition of weight at most $n+q2^{q-1}$ into at most $2^q$ rectangles.Given the claim, we can derive the lemma as follows. By applying the claim to each of the matrices $B_i$, we obtain a decomposition of $A$ of weight at most $(m/q)(n + q2^{q-1})$. Now take $q:=\lfloor \log n - 2\log\log n\rfloor$. For this choice of $q$, we have $m/q\leq (1+o(1))m/\log n$ and $n+q2^{q-1}\leq (1+o(1)) n$. So, the weight of the decomposition is at most $(1+o(1))nm/\log n$, and the the total number of rectangles is at most $\ell\cdot t\leq (m/q)\cdot 2^q=(m/q)(n/\log^2 n) \approx (nm/\log^3)$.
It remains to prove the claim. Let $B$ be a boolean $n\times q$ matrix. Split the rows of $B$ into groups, where the rows in one group all have the same values. This gives us a decomposition of $B$ into $t\leq 2^q$ rectangles. For the $i$-th of these submatrices, let $r_i$ be the number of its nonzero rows, and $c_i$ the number of its nonzero columns; hence, the submatrix is an $r_i\times c_i$ rectangle. Since each nonzero row of $B$ lies in exactly one of the these matrices, the weight of the decomposition is \[ \sum_{i=1}^t (r_i+c_i)\leq p+\sum_{k=0}^q\sum_{i:c_i=k}k \leq p+\sum_{k=0}^q\binom{q}{k}\cdot k = p+q2^{q-1}\,. \] $\Box$