A simple Knight's problem
GNU Octave, 55 56 58 78 87* 93 chars

a=t(:,1);b=t(:,2);-4*max(2*(g=a.*b)-3*(a+b)+4,0)+g.*--g


Octave doesn't take input from STDIN, so you've got to provide the input in the program:

t = [
    1 7;
    2 2;
    2 3;
    4 5;
    5000 6000 
];                % test cases

a=t(:,1);b=t(:,2);-4*max(2*(g=a.*b)-3*(a+b)+4,0)+g.*--g


The logic is as follows:

nchoosek(n*m, 2) gives us the number of combinations of two positions we can have on a N*M board. We then multiply it by two since we have two different knights.

Then we work out how many 3*2 blocks fit in an N*M board. For each 3*2 block there are 4 different positions our knights can be attacking each other. So we multiply it by 4 and subtract it from the value we calculated above.

*thanks to a simplification of the nchoosek I shamelessly stole from Matt.

Edit

I've just tested this on my laptop to make sure it meets the time requirements.

It will compute 500,000 10,000,000 test cases in an average of 0.918787 0.231201 seconds