When using two factor authentication on any website you should always keep your recovery codes printed out or saved somewhere secure (preferably encrypted).
If you find that you’ve lost your recovery codes and have no access to your 2FA app due to losing/resetting your phone, you can potentially generate new recovery codes by logging in on a device that has your session saved and resetting your 2FA device.
If you have an SSH connection still available, you can also generate new recovery codes using that: https://docs.gitlab.com/ce/user/account/two_factor_authentication.html#generate-new-recovery-codes-using-ssh
If neither of those work, you can contact support at gitlab.com with a form of identification and your user information, and we’ll reset your 2FA. This is a last-ditch solution, and may not be available in the future due to the potential holes it opens for social engineering.
If you’re not on GitLab.com, you can contact your instance administrator for assistance.