Just realized that you are asking for the case that $|M|=|N|=d$. Then you can do matrix multiplication, right? Write $M$ is a row matrix $X$, $N$ as a column matrix $Y$, negate the entries of $Y$, and compute the matrix $Z=XY$. Clearly, the $z_{i,j}$ is the Hamming distance between the $i$th point of $M$ and the $j$th point of $N$. According to the last breakthroughs this has running time $O(d^{2.3727})$ (but I have a 50,000 pages manuscript that shows how to do this matrix multiplication in $O(d^{2.3726999999})$ time by a really simple algorithm).
You can get similar effect if the matrices are not squares. I think Uri Zwick has a paper about fast matrix multiplication in this case.
In some sense, this is not too interesting - we want to avoid the $O(|M| * |N|)$ term. The improvements in the $d$ term are kind of meh, meh...