Bem, é quase como se você respondesse à sua própria pergunta.
Parece que você não o instalou por meio do gerenciador de pacotes, portanto, usar apt-get
não vai te levar muito longe. É por isso que não é possível encontrar o pacote, pois ele não sabe nada sobre isso.
O caminho ~/genymotion
não existe desde que você disse que está armazenado em /home/sandip/downloads/genymotion
.
Portanto, tente usar o instalador, pois ele tem uma opção uninstall
sudo /path/to/genymotion-x.x.x_x64.bin --uninstall