Let $m^2+5n = (m+a)^2 = m^2+2am+a^2 \Longrightarrow 5n = a^2+2am$ and let $n^2+5m = (n+b)^2 = n^2+2bn + b^2 \Longrightarrow 5m = b^2+2bn$. Now if $a,b \geq 3$, we have $$5n = a^2 + 2am >6m>5m$$$$5m = b^2+2bn>6n>5n$$contradiction. So WLOG $a \leq 2$. If $a = 1$: $5m=b^2+2bn \Longrightarrow 5(2m+1) = 2b^2+4bn+5 \Longrightarrow 25n=2b^2 + 4bn+5 \Longrightarrow n = \frac{2b^2+5}{25-4b}$ Now by checking few cases we have $b=5,6$ gives solutions $\boxed{(m,n) = (27,11);(77,192)}$. If $a=2$ $5m=b^2+2bn \Longrightarrow 5(4m+4) = 4b^2+8bn+20 \Longrightarrow 25n= 4b^2 + 8bn +20 \Longrightarrow n = \frac{4b^2+20}{25-8b}$ Now by checking few cases we have $b=2,3$ gives solutions $\boxed{(m,n) = (4,4);(56,69)}$. Hence all solutions are $\boxed{(m,n)=(4,4);(27;11);(56,69);(77,192)}$ and permutations.