Try

apt-get --force-yes purge mysql-server phpmyadmin

As phpmyadmin needs mysql - maybe it won't let you remove mysql without removing phpmyadmin also

Sounds strange what about running apt-get autoremove and apt-get install -f first

Same...

Reading package lists... Done
Building dependency tree       
Reading state information... Done
Package 'mysql-server' is not installed, so not removed
The following packages will be REMOVED:
  phpmyadmin
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
1 not fully installed or removed.
After this operation, 25,0 MB disk space will be freed.
Do you want to continue? [Y/n] y
(Reading database ... 1279252 files and directories currently installed.)
Removing phpmyadmin (4:4.5.4.1-2ubuntu1) ...
dpkg: error processing package phpmyadmin (--remove):
 subprocess installed post-removal script returned error exit status 10
Errors were encountered while processing:
 phpmyadmin
E: Sub-process /usr/bin/dpkg returned an error code (1)