I used the "-ErrorAction SilentlyContinue" solution but then later ran into the problem that it leaves an ErrorRecord behind.  So here's another solution to just checking if the Service exists using "Get-Service".  
# Determines if a Service exists with a name as defined in $ServiceName.
# Returns a boolean $True or $False.
Function ServiceExists([string] $ServiceName) {
    [bool] $Return = $False
    # If you use just "Get-Service $ServiceName", it will return an error if 
    # the service didn't exist.  Trick Get-Service to return an array of 
    # Services, but only if the name exactly matches the $ServiceName.  
    # This way you can test if the array is emply.
    if ( Get-Service "$ServiceName*" -Include $ServiceName ) {
        $Return = $True
    }
    Return $Return
}
[bool] $thisServiceExists = ServiceExists "A Service Name"
$thisServiceExists 
But ravikanth has the best solution since the Get-WmiObject will not throw an error if the Service didn't exist. So I settled on using:
Function ServiceExists([string] $ServiceName) {
    [bool] $Return = $False
    if ( Get-WmiObject -Class Win32_Service -Filter "Name='$ServiceName'" ) {
        $Return = $True
    }
    Return $Return
}
So to offer a more complete solution:
# Deletes a Service with a name as defined in $ServiceName.
# Returns a boolean $True or $False.  $True if the Service didn't exist or was 
# successfully deleted after execution.
Function DeleteService([string] $ServiceName) {
    [bool] $Return = $False
    $Service = Get-WmiObject -Class Win32_Service -Filter "Name='$ServiceName'" 
    if ( $Service ) {
        $Service.Delete()
        if ( -Not ( ServiceExists $ServiceName ) ) {
            $Return = $True
        }
    } else {
        $Return = $True
    }
    Return $Return
}