DFT/FFT: What did N stand for again?
Your image is M rows x N cols, and a 2D FFT requires 1D FFTs on all rows followed by 1D column-wise FFTs on the result.

So you have:

$M N \log N + N M \log M = MN (\log M + \log N) = MN \log MN$ 

operations in total.

The DFT case can be derived using a similar method - this is left as an exercise for the reader.