Это просто звонок:
net stop "MyService"
intallutil.exe /u MyService.exe
// Copy your exe into place
installutil.exe MyNewService.exe
// optional
net start "MyService"
Это останавливает старую службу, удаляет ее, затем копирует новую на место, устанавливает и (необязательно) запускает ее.
Большинство инсталляторов делают это довольно легко. Единственный другой «уловка» - убедиться, что ваш установщик ограничен в установке на локальный диск, а не в сетевой путь, если служба будет установлена для автоматического запуска при запуске.