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 188.8.131.52 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.