Wolfram Language (Mathematica), 652402 bytes
Saved 250 bytes thanks to @py3_and_c_programmer.
This was originally a fastest-code challenge. Now it became a code-golf, but I'm too lazy to golf it.
f[m_, n_] := Total@LinearProgramming[Table[=Total@LinearProgramming[Table[-1, m*n], SparseArray[ Flatten@MapIndexed[SparseArray[Flatten@MapIndexed[{#2[[1]], #} -> 1 &>1&, Flatten[{Table[ m*i + j + k + 1Table[m*i+j+k+1, {i, 0, n - 1}, {j, 0, m - 3}, {k, 0, 2}], Table[ m*Table[m*(i + ki+k) + j + 1+j+1, {i, 0, n - 3}, {j, 0, m - 1}, {k, 0, 2}], Table[ m*Table[m*(i + ki+k) + j + k + 1+j+k+1, {i, 0, n - 3}, {j, 0, m - 3}, {k, 0, 2}], Table[ m*Table[m*(i + ki+k) + j +j- k + 1k+1, {i, 0, n - 3}, {j, 2, m - 1}, {k, 0, 2}]}, 2], {2}], {(m - 2) n + m n+m(n - 2) + 2 +2(m - 2) (n - 2), m*n}], Table[{2, -1}, (m - 2) n + m n+m(n - 2) + 2 +2(m - 2) (n - 2)], Table[{0, 1}, m*n], Integers] Using the built-in LinearProgramming. Gives the results from 1x1 to 9x9 in 40 seconds on TIO.