If you have UAC enabled, you need to be running from an already elevated command prompt for service installation and removal to succeed. Manipulating the Service Control Manager requires elevated privileges.
It seems the preferred method for doing this is ShellExecute() with the runas verb, but that would involve a second process. There is a way to use COM objects to keep it in once process. I think tat is over complicating it. Perhaps a hidden option or an alternative entry function besides main() (and whatever win32 api trickery is needed to call that) combined with ShellExecute is the way to go.
To clarify, UAC is not needed to run mongo as a service, just install or remove it.