gitlab preinstall: It is required to upgrade to the latest 12.10.x version first before proceeding.

This is how I fixed it.

I went to about.gitlab.com/releases/categories/releases and looked up the latest 12.10.x release, which was 12.10.8.

Then I typed

apt install gitlab-ce=12.10.8-ce.0

if you happen to have the enterprise edition installed, you might want to change the ce to ee:

apt install gitlab-ee=12.10.8-ee.0

After that I could update to the latest gitlab version by simply typing

apt install gitlab-ce

or, again, if you have the enterprise edition installed, change the ce to ee:

apt install gitlab-ee