GitLab was unable to verify the custom domain, their suggested entries didn’t seem to work.
Using the following worked:
sub = Your subdomain (or @ for root)
sub 1800 IN A 22.214.171.124 sub 1800 IN TXT "gitlab-pages-verification-code=###CODE###"
Make sure to double check the IP for GitLab pages.
Note: This failed after switching to CloudFlare, which accepted the GitLab suggested input and verified within minutes.