I wanted a solution to this that works on both Linux and on Windows (with Cygwin binaries on the path.) - my Vim config is shared between the two.
One problem is that 'mkdir' is, I think, built-in to the cmd shell on windows, so it can't be overridden by putting the Cygwin mkdir executable earlier in the path.
I solved this by invoking a new bash shell to perform the action: From there, 'mkdir' always means whatever mkdir executable is on the path:
!bash -c "mkdir -p ~/.vim-tmp"
However, this has the problem that. on Windows at least, it pops up a new window for the cmd shell that '!' invokes. Don't want that every time I start vim. Then I discovered the vim function 'system', which invokes a new cmd shell (the icon appears in the Windows taskbar) but the window is minimised. Hence:
call system("bash -c \"mkdir -p ~/.vim-tmp\"")
Ugly but works.