It's possible that your slow pulls were due to the initial storage format being inefficient for very branchy repositories. I've documented migrating to generaldelta to solve this here: https://book.mercurial-scm.org/read/scaling.html#scaling-rep...
Additionally, using the 'clonebundles' feature, it's possible to speed up your initial clone by a huge amount (making it way faster than non-clonebundles Mercurial or Git): https://book.mercurial-scm.org/read/scaling.html#improving-s...
Of course, this is too late for you, I guess...
They always measure Mercurial pull performance using a load tests. For example between 4.2.X and 4.4.X version of our software we went form 1.8s to 1.4s average time for a pull to happen under load.
We only do this via HTTP since this can be really optimized for speed. So having to take minutes sounds like some backend problems like overloaded server, not enough workers to handle connection etc.
Part of the reason for the move is that we wanted to take advantage of the corp-wide infrastructure of an Atlassian stash server hosted in the cloud and professionally maintained, so as to get away from maintaining our own repo.
But the speeds I quote above were for the initial phase of the conversion, when both repos ran on the same ESX VM and direct comparisons were meaningful. Now that its hosted professionally in the cloud, it seems even faster.
Note that I'm across ~2500 miles of VPN from the home office, and that surely has something to do with it.
The initial clone time for hg and git is within the same order of magnitude (order of an hour), though git manages to be about 50% faster at that too.
Why do you need to keep all 25 years of commits?
Our team just moved from hg to git for an enormous project that has ~25 years of history (CVS -> SVN -> hg|git). The biggest improvement to my daily life is that a git pull takes seconds, while an hg pull takes minutes (or even large fractions of hours when I've spent a week or two away from work).