Esta resposta deve ser tentada também para o Ubuntu 16.04, aconselho tentar em segundo lugar:
cd /var/lib/dpkg/info/
sudo rm -r phpmyadmin.*
sudo apt-get clean
sudo apt-get update
phpdismod mcrypt mbstring
service apache2 restart
sed -i 's/Include \/etc\/phpmyadmin\/apache.conf/ /g' /etc/apache2/apache2.conf
apt-get purge phpmyadmin -y
apt autoremove