How do I set the UI language in vim?

As Ken noted, you want the :language command.

Note that putting this in your .vimrc or .gvimrc won’t help you with the menus in gvim, since their definition is loaded once at startup, very early on, and not re-read again later. So you really do need to set LC_ALL (or more specifically LC_MESSAGES) in your environment – or on non-Unixoid systems (eg. Windows), you can pass the --cmd switch (which executes the given command first thing, as opposed to the -c option):

gvim --cmd "lang en_US"

As I mentioned, you don’t need to use LC_ALL, which will forcibly switch all aspects of your computing environment. You can do more nuanced stuff. F.ex., my own locale settings look like this:

LANG=en_US.utf8
LC_CTYPE=de_DE.utf8
LC_COLLATE=C

This means I get a largely English system, but with German semantics for letters, except that the default sort order is ASCIIbetical (ie. sort by codepoint, not according to language conventions). You could use a different variation; see man 7 locale for more.

Try this in _vimrc. It works with my win7.

set langmenu=en_US
let $LANG = 'en_US'
source $VIMRUNTIME/delmenu.vim
source $VIMRUNTIME/menu.vim

For reference, in Windows (7) I just deleted the directory C:\Program Files (x86)\Vim\vim72\lang. That made it fallback to en_US.