Você pode definir uma nova senha de root com
sudo dpkg-reconfigure mysql-server-5.x
Substitua x pela versão que você instalou.
Em seguida, tente efetuar login novamente (se você colocar a senha após a opção -p, certifique-se de que não haja espaço entre -p e sua senha, ou seja, se sua senha for olá, faça login com mysql -u root -phello )