O comando abaixo remove o MySQL e todas as suas dependências completamente.

apt-get remove --purge 'mysql-.*'