Мог заставить его работать после установки следующим образом:
sudo add-apt-repository -y ppa:tortoisehg-ppa/releases
sudo apt-get update
sudo apt-get install mercurial tortoisehg
Из этого ответа: https://stackoverflow.com/questions/5627414/correct-way-to-install-mercurial- на убунту