Eu entendo que você instalou manualmente o MySQL, sem usar o apt. Qualquer programa que você instalar manualmente não é registrado pelo apt, então o apt não pode removê-lo.
Você pode impedir que o MySQL inicie parando o MySQL e depois removendo o script de inicialização.
sudo update-rc.d -f mysql.server remove
Substitua mysql.server
pelo nome do script de inicialização do MySQL.
Agora o MySQL está parado, você pode remover o usuário:
sudo deluser mysql
A única coisa que resta são os arquivos do MySQL. Se você quiser economizar espaço, você pode removê-los.