<s>[INST] $(2^m -1)(2^n-1)$ divides $(2^{mn} -1)$ if and only if $\gcd(m,n) = 1$. If $\gcd(m,n) = 1$ then $(2^m-1)(2^n-1)$ divides $2^{mn} - 1$ because each of $2^m-1$, $2^n-1$ divide $2^{mn}-1$ and $\gcd(2^m-1, 2^n-1) = 2^{\gcd(m,n)}-1 = 1$. How about the converse? If $\gcd(m,n) > 1$, can one show that $(2^m-1)(2^n-1)$ does not divide $(2^{mn}-1)$?
 [/INST] Here's another proof I found. First we need the following:
Lemma  If $m,n$ are positive integers with $m > n$, then $(2^m - 1)(2^n-1) \mid (2^{mn}-1)$ implies $(2^{m-n}-1)(2^n-1) \mid (2^{(m-n)n} - 1)$.
Proof of lemma. $(2^m-1)(2^n-1) \mid (2^{mn}-1)$ is equivalent to $(2^{mn} - 1)/(2^m-1) \equiv 0 \pmod{2^n-1}$. Using $2^m \equiv 2^{m-n} \pmod{2^n-1}$ we have 
$(2^{mn} - 1)/(2^m-1) \equiv 2^{m(n-1)} + 2^{m(n-2)} + \cdots 2^m + 1 \equiv 2^{(m-n)(n-1)} + 2^{(m-n)(n-2)} + \cdots  2^{m-n} + 1 \equiv (2^{(m-n)n} - 1) / (2^{m-n}-1) \pmod{2^n-1}$. 
Thus $(2^{(m-n)n} - 1) / (2^{m-n}-1) \equiv 0 \pmod{2^n-1}$ which is equivalent to the stated conclusion.
Now to our main task. Suppose $m$, $n$ are positive integers with $\gcd(m,n) = d$.  By a well-known algorithm to compute the greatest common divisor, there is a sequence $(m_1,n_1), (m_2, n_2), \ldots, (m_k, n_k)$ such that: $(m_1, n_1) = (m, n)$, $(m_k, n_k) = (d, d)$, $m_i \not= n_i$ for $1 < i < k$ and 
$(m_{j+1}, n_{j+1}) =  (m_j-n_j,n_j)$ if $m_j > n_j$, $(m_{j+1}, n_{j+1}) = (m_j, n_j-m_j)$ if $n_j > m_j$ for $1 \leq j < k$.
If $(2^m-1)(2^n-1) \mid (2^{mn}-1)$ then using the lemma one shows by induction $(2^{m_j}-1)(2^{n_j}-1) \mid (2^{m_jn_j}-1)$ for all $j$ in the range $1 \leq j \leq k$. For $j =k$, this means $(2^d-1)(2^d-1) \mid (2^{d^2}-1)$ which is equivalent to $(2^{d^2}-1)/(2^d-1) \equiv 0 \pmod{2^d-1}$.  But $(2^{d^2}-1)/(2^d-1) \equiv 2^{d(d-1)} + 2^{d(d-2)} + \cdots + 2^{d} + 1$. Since $2^d \equiv 1 \pmod{2^d-1}$, the latter sum is $\equiv d \pmod{2^d-1}$, and we conclude $d \equiv 0 \pmod{2^d-1}$, which happens only when $d = 1$. End of proof.
</s>