Thought Process
I recreated the game and essentially did a Breadth First Search to solve for small cases of S(m, n). Below I give my code, this was a fun problem in itself, but not very difficult.
From this some obvious patterns emerged
m = 2
S(2, 2) = 5
S(2, 3) = 9 (+4)
S(2, 4) = 15 (+6)
S(2, 5) = 21 (+6)
S(2, 6) = 27 (+6)
m = 3
S(3, 3) = 13
S(3, 4) = 17 (+4)
S(3, 5) = 23 (+6)
S(3, 6) = 29 (+6)
S(3, 7) = 35 (+6)
S(3, 8) = 41 (+6)
m = 4
S(4, 4) = 21
S(4, 5) = 25 (+4)
S(4, 6) = 31 (+6)
S(4, 7) = 37 (+6)
m = 5
S(5, 5) = 29
S(5, 6) = 33 (+4)
S(5, 7) = 39 (+6)
Essentially, we have the following:
This was not surprising as I anticipated a recursive solution since after some moves a board can essentially result in a smaller board (cutting off the useless parts which we will no longer touch).
From here, you can either notice more patterns or count solutions manually in many ways, I went the following path to get the answer. Take note of this page: https://proofwiki.org/wiki/Square_Modulo_8 to understand the first line.
Interactive Code
Enter a number (yourinput)
Code will output the number of grids such that S(m, n) = p*p where p < yourinput