on the Route page it says "Add a new public hostname or private network. Then, select a tunnel to route the traffic."

It sounds like you tried to put your GitLab on a second-level or deeper subdomain (i.e gitlab.internal.example.com) when the Universal SSL Cert (the one Cloudflare gives you for free) only covers first-level subdomains (like gitlab.example.com). You can get around this by purchasing Advanced Certificate Manager (ACM) and turning on Total TLS or issuing an Adv. Cert for that deeper subdomain, or just by moving your Gitlab to a 1st level subdomain like shown in the tutorial.