Figured it out. Have to use a Gitlab admin account (wasn't aware there was such a thing since I didn't install Gitlab).
Can do this either with the default admin account (admin@local.host) or by elevating another user to admin. This can be done via SSH by opening a Rails console on Gitlab and setting user.admin = true then user.save.
See https://forum.gitlab.com/t/how-to-reset-the-admin-password-via-the-rails-console/223
Personally (on Gitlab 6.3) I had issues resetting the original admin password because the query generated by the save method had a condition for id != 1, so it was easier to just make another admin account instead of trying to work around that.