Since finding all possible expressions $$ M^2 + N^2 = m^2 + n^2$$ will in fact give you a complete factorization of $m^2 + n^2,$ all you need to know is how to create all $(M,N)$ pairs from a complete prime factorization of $m^2 + n^2 = p_1 p_2 p_3 \ldots p_r q_1^2 q_2^2 \ldots q_s^2,$ where the $p_i \equiv 1 \pmod 4,$ while all $q_j \equiv 3 \pmod 4,$ and the labeled primes are not necessarily distinct. Each prime $p_i$ has essentially one representation as the sum of two squares, at least when positive and ordered. Then you just use $$ (a^2 + b^2) (c^2 + d^2) = (a c + b d)^2 + ( a d - b c)^2$$ while putting in $\pm$ signs on $a,b,c,d$ and switching order. For each expression, you just multiply through by all the $q_j.$ The $q_j$ must, of course, appear as factors of $\gcd(m,n).$
The general method for any $x^2 + k y^2 = t,$ for some $k \geq 1,$ is the Hardy-Muskat-Williams algorithm, which is implemented in some CAS, sometimes correctly. Given any $p_i,$ the first task in solving $u^2 + v^2 = p_i$ is finding a square root of $-1 \pmod {p_i}.$ The rest of this is treated in Editor's Corner: The Euclidean Algorithm Strikes Again by Stan Wagon, M.A.A. Monthly,Vol. 97, No. 2 (Feb., 1990), pp. 125-129. The first page can be seen at this link. However, the way I would do it is to take the integer with $w^2 \equiv -1 \pmod {p_i},$ or $w^2 + 1 = p_i t,$ write down the positive quadratic form $\langle p_i, 2 w, t \rangle$ and keep track of each step as I reduce it to $\langle 1,0,1 \rangle,$ reversing steps to find a representation $u^2 + v^2 = p_i.$ Although, as I think of it, I actually do the whole thing by matrix multiplication anyway.
Meanwhile, there is a very nice note on using multiple expressions as the sums of two squares to factor a number, in the M. A. A. Monthly, December 2009, pages 928-931, A Note on Euler's Factoring Problem by John Brillhart.
