$(2^m -1)(2^n-1)$ divides $(2^{mn} -1)$ if and only if $\gcd(m,n) = 1$.

I'm going to write this proof in the style in which I found it and leave it to someone else to translate it into more usual number-theoretic language.

We have

$$(2^{mn}-1)/(2^m-1)=1+2^m+2^{2m}+\dotso+2^{(n-1)m}=1\overbrace{\underbrace{0\ldots0}_{m-1}1\ldots1\underbrace{0\ldots0}_{m-1}1}^{n-1}{}_2$$

and

$$2^n-1=\overbrace{1\ldots1}^n{}_2\;.$$

The question is whether the first of these is divisible by the second. Adding the second pattern into the first such that its least significant digit is aligned with a $1$ shifts that $1$ upward by $n$ digits.

Now if $\gcd(m,n)$, then successively shifting all $1$s except the most significant $1$ past the latter puts them all into different digits. That leaves $n$ consecutive $1$s, i.e. a power of $2$ times $2^n-1$.

This won't work if $\gcd(m,n)\gt1$ because in that case some of the $1$s would land on top of each other. So what we want to show is that if the first number were divisible by the second one, it would have to be possible to gather all the $1$s together.

So assume that $k\cdot\overbrace{1\ldots1}^n{}_2=1\overbrace{\underbrace{0\ldots0}_{m-1}1\ldots1\underbrace{0\ldots0}_{m-1}1}^{n-1}{}_2$. Let $r=2^s$ be some power of $2$ greater than $k$. Then $(r-k)\cdot\overbrace{1\ldots1}^n{}_2+1\overbrace{\underbrace{0\ldots0}_{m-1}1\ldots1\underbrace{0\ldots0}_{m-1}1}^{n-1}{}_2=r\cdot\overbrace{1\ldots1}^n{}_2=\overbrace{0\ldots0}^s\overbrace{1\dotso1}^n{}_2$. Now consider the binary representation of $r-k$. Each of its digits represents adding $n$ consecutive $1s$ at the corresponding digit of the result. Going from the least to the most significant digit, each of these additions must move the least significant remaining $1$ upward by $n$ digits, because if it skips a $1$, that $1$ can never be cancelled again, and if it adds to a $0$ instead, the resulting $1$ can also never be cancelled again. Also, a $1$ may never land on another $1$, since that would reduce the number of $1$s and the process can't generate any new ones, so we couldn't end up with $n$ consecutive $1$s anymore.

Thus, the additions would have to move the $1s$ in a manner that's impossible if $\gcd(m,n)\gt1$, so in this case $(2^{mn}-1)/(2^m-1)$ is not divisible by $2^n-1$, and hence $2^{mn}-1$ is not divisible by $(2^m-1)(2^n-1)$.