A standard argument (Lemma 3.1 here) shows that the cut-norm is 4-equivalent to the operator norm from $\ell_{\infty}^m$ to $\ell_1^n=(\ell_\infty^n)^*$. Therefore the volume you ask is almost the same (up to a factor $4^{mn}$) as the volume of the unit ball in the projective tensor product $\ell_{\infty}^m \otimes_\pi \ell_\infty^n$. This is exactly this question (at least for $m=n$), and I gave an answer saying basically that (from general theorems) your lower bound on $V(m,n)^{1/mn}$ is sharp up to a logarimthic factor.

I guess this logarithm is not necessary, but I don't know how to remove it.

A standard argument (Lemma 3.1 here) shows that the cut-norm is 4-equivalent to the operator norm from $\ell_{\infty}^m$ to $\ell_1^n=(\ell_\infty^n)^*$. Therefore the volume you ask is almost the same (up to a factor $4^{mn}$) as the volume of the unit ball in the projective tensor product $\ell_{\infty}^m \otimes_\pi \ell_\infty^n$. This is exactly this question (at least for $m=n$), and I gave an answer saying basically that (from general theorems) your lower bound on $V(m,n)^{1/mn}$ is sharp up to a logarimthic factor.

I guess this logarithm is not necessary, but I don't know how to remove it.