Noam Elkies, however, gave the following reply:
4 * [ sin^2(a pi / 2 m) + sin^2(b pi / 2 n) ]
where a,b are nonnegative integers, not both zero, and less than m,n respectively.
A few further notes about these numbers: if (say) m is given then the number of spanning trees as a function of n satisfies a constant linear recurrence; for instance if m=2 the counts are 1, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, ... satisfying c(n) = 4 c(n-1) - c(n-2). Finally, the number of *square* mazes is itself a square up to small factors; for instance there are
2^34 3^2 5^3 11^4 19^4 41^2 59^2 101^2 181^2 281^2
square mazes of order 10.
ObPuzzles: