Tente usar o cygrunsrv para remover serviços. Depois disso, normalmente, apenas excluo todo o diretório cygwin, embora isso não limpe as entradas de registro ou de menu inicial.
(Se você já deletou a pasta cygwin, então o cygrunsrv obviamente não funcionará.)