O Wine tem uma interface para desinstalar o software, basta executar winecfg . Se isso não funcionar, você pode remover o diretório .wine em sua pasta pessoal, mas isso removerá qualquer programa instalado usando o wine.
Eu acho que você deveria dar uma olhada no playonlinux. Ele oferece a possibilidade de usar diferentes versões de vinhos para diferentes programas e desinstalar facilmente o software, pois cada programa possui seu próprio ambiente, que pode ser excluído como um todo, para que você não precise desinstalar nenhum software.