Look only at numbers $m,n$ being powers of a same prime, say $2$, so $m^an^b = (2^u)^a(2^v)^b = 2^{ua + vb}$, with $u,v \geq 1$, and has exactly $ua +vb + 1$ positive divisors. I claim that any number $r \geq ab+1$ may be written as some $ua+vb$. Consider the $b$ numbers $r-a > r-2a > \cdots > r-(b-1)a > r-ba \geq 1$. They all yield different remainders modulo $b$, since if $b \mid (r-ia)-(r-ja)$ then $b \mid |i-j|a$, impossible, as $\gcd(a,b)=1$ and $|i-j| < b$. It follows that one of them, say $r-ua$, is divisible by $b$, so $r-ua = vb$ for some $v\geq 1$. Now, $ab$ cannot obviously be written in such a way. If we show it cannot in any other way we choose $m,n$, then the least value of $k$ required will be $k=ab$. If $m,n$ are not powers of a same prime, then there will exist at least two primes $p\neq q$ dividing $m^an^b$, and since $m,n > 1$, it follows the exponents of $p$ and $q$ are at least $a$, respectively $b$, inducing at least $(a+1)(b+1) = ab+a+b+1 > ab+1$ divisors. We are done. Notice this is not exactly equivalent to Frobenius' stamp problem (also known as Sylvester's problem), since the coefficients of the linear combination in $a$ and $b$ are not allowed to be zero, from $m,n>1$. That is why the lower bound of $ab-a-b+1$ from Sylvester's problem had to be increased to $ab+1$. The method of proof however is almost identical.