GitLab の Clone URL などに表示されているアドレス内のホスト名は、設定ファイル gitlab.yml に記述されたものが使用されます。
この設定ファイルは、パッケージを使って GitLab をインストールした場合は、以下の場所にあります。
/opt/gitlab/embedded/service/gitlab-rails/config/gitlab.yml
...
host: YourHostName # これを変更変更後、以下のように GitLab 関連のサービス群を再起動すれば、新しいホスト名が反映されます。
$ sudo gitlab-ctl restart