Edit: Encontrei a solução oficial do site da Genymotion: Remova todos os dispositivos virtuais usando do Genymotion (infelizmente, você excluiu o VirtualBox, portanto, simplesmente exclua as imagens do disco na sua pasta de instalação.
Exclua o diretório de instalação do Genymotion executando
sudo rm -r ~/genymotion
(se instalado em seu diretório inicial).
Exclua os diretórios de dados do Genymotion executando
sudo rm -fr ~/.Genymobile ~/.config/Genymotion.
Altere os caminhos das pastas com base em onde eles estão. Mostrar arquivos ocultos com Ctrl-H no Nautilus.
Deve ser perfeitamente seguro remover os arquivos .bin da sua área de trabalho.