Instale o gerenciador de pacotes Synaptic:
sudo apt install synaptic
Abra o gerenciador de pacotes Synaptic e procure por "wine" na barra de pesquisa. Remova todos os pacotes que estão marcados. Veja esta imagem para um exemplo (eu procurei por "eclipse" neste caso):
Em seguida, reinicie sua máquina e execute o comando:
sudo apt autoremove