In every step one of the variables is divided by 2, so I think the depth must be $\log n + \log m$. So the solution is $O(nm(\log n + \log m))$
However for some reason an article I am reading claims for some problem that it should be $O(nm(\log n \log m))$
so either my idea for the solution of this recurrence is wrong, or the recurrence I used to describe the problem is wrong.