Se você não tem nenhum outro software rodando abaixo do wine, você pode simplesmente remover toda a pasta de vinhos escondida no seu diretório $ HOME digitando em um terminal:
rm -rvf $HOME/.wine
A pasta será recriada da próxima vez que você tentar instalar outros programas em vinho, então não se preocupe. Mas se você não gostar dessa opção, basta pesquisar a estrutura de arquivos do programa e excluir sua pasta:
nautilus $HOME/.wine/drive_c
Seu programa deve estar em "Arquivos de Programas" ou em algum local habitual do Windows como esse. Depois disso, se você quiser remover os ícones gerados pelo instalador, poderá encontrá-los em algum lugar:
nautilus $HOME/.local/share/applications/wine