mv first tries to rename("/mnt", "/mnt/foo") and only after that fails with EXDEV it decides to mkdir("/mnt/foo")
To me this looks like a bug: the order of the checks has been reversed. mv should never attempt to put a directory into itself, since there is no situation in which that ever makes sense. Only after that check passes should it decide if rename() is enough, or if it has to do a copy/delete.
The problem here is that the error conditions are not mutually exclusive - it is possible to have a rename cross devices and attempt to move a directory into one of its descendants - but there's no specification in the standard[1] of which error should be returned in such a case. The priority of non-mutually-exclusive errors is seldom considered, yet this is a good example of why it's important.
In other words the "rename("/mnt", "/mnt/foo")" should have failed with EINVAL, not EXDEV. A look through the Linux source shows that at least there, cross-device has higher priority than parent-descendant: http://lxr.free-electrons.com/source/fs/namei.c#L4240
[1] http://pubs.opengroup.org/onlinepubs/9699919799/functions/re...