You're right--you need to re-formulate your statements. For the most straightforward (but not the most elegant) method, break it up into two conditions: (1) m, n both even, and (2) m, n both odd. Then prove the statement for each case. That is, first prove (both directions) that 4 divides m^{2}-n^{2}if and only if m, n both even. Then show 4 divides m^{2}-n^{2}if and only if m, n both odd (each direction, of course). It may involve more pencil lead, but I believe it makes the logic more transparent and less likely to be inaccurately manipulated.

If you choose to do anything by contrapositive in these cases, the negation of "m, n both odd" becomes "either m or n is not odd," and likewise with "even".

Also, when you want to represent m and n as generic integers, it is customary to use alternate letters. For example, let m be an even integer represented by 2r, and n an even integer represented by 2s, for all integers r, s.