I've done this one a few times and forgot to document each time.
The issue is that the instructions are confusing.
Under Deploy > Pages, you would add your domain, to check on the verification you can navigate back to the domain in question from here.
When you add the domain, it opens up a "Pages Domain" page with the DNS records needed for the domain verification. The issue here, is the instructions are confusing. Each time that I've put the info in exactly -- it fails. Every time.
I'm sure each time, I've resolved it differently, but here's what worked the last time. There will be two DNS records: the ALIAS and the domain verification record. The ALIAS record is fine. The domain verification record is where the issue is. It will be displayed as:
_gitlab-pages-verification-code.<'DOMAIN'> TXT gitlab-pages-verification-code=<'VERIFICATION CODE'>
Entering it this way on Namecheap, causes it to fail. I've also tried just using '_gitlab-pages-verification-code.' in the host field - this also did not work.
What worked for me was to use the DOMAIN in the host field and the verification as is in the TXT value for the record. Wait for the TTL to expire on the old record and check again, but it should verify automatically.