Yes, you can install new services. Just install it like you would in an installer. Normally this means calling your service exe with special commandline arguments. Like "MyService.exe /install"
Specifically you would do this by including a batch file in your update and from that batch file calling the install argument for that executable.
Does that make sense?
I can give you more specific advice if you tell me what language you used for your service and how you typically install it.