Maybe just support hg-git? All someone has to do is write some tests for Gitlab, and then you are all set?

Interesting, feel free to make a detailed technical feature proposal on https://gitlab.com/gitlab-org/gitlab-ce/issues and mention me.

hg-git already works with gitlab, doesn't it?

I was having problems even cloning using hg-git + ssh.

There's no real limitations on making the two VC system compatible, that's why RhodeCode has same functionality for both Git and Mercurial, without making tradeoffs, that's why systems like hg-git could also work out quite well.