Working mod 3 then both m and n are multiples of 3.  Then 9 can be factored out of both sides of the equation, leaving a reduced equation (3m'+4n')*(4m'+3n')=3^61.

So then we can reapply this process until one of the factors is reduced to 1 to find a primitive solution to (3m+4n)*(4m+3n)=3^p.

Without loss of generality let 3m+4n=1 and 4m+3n=3^p.  Then 

m = (4*3^p - 3) / 7 and n = (-3*3^p + 4) / 7

So now we need 4*3^p - 3 = 0 mod 7 for integer solutions.

Simplifying the congruence we get 3^p = 6 mod 7.  This happens when p is of the form 6q+3.

p=6q+3 is odd and so is our target exponent of 63; and since any primitive solution can be scaled up to a solution for an exponent 2 higher, then any primitive solution below 63 can be scaled up.  So all primitive solutions below p=63 will yield a corresponding solution for p=63.

So then the primitive solutions of (3m+4n)*(4m+3n)=3^p can be parameterized as 

{m, n, p} = {(4*3^(6q+3)-3)/7 , (-3*3^(6q+3)+4)/7 , 6q+3}

The smallest q is q=0, which yields {m,n,p} = {15,-11,3} which Larry found in his exploration.  q can go all the way to 10, for p=63.  So then there are 11 valid values of q for the problem.  Add the fact that the original equation is symmetric in m and n then we can double that; so there are 22 pairs of integers (m,n) satisfy the equation.