Pieter was correct.
It was messing up due to the custom loop I was running on the archive page. I removed the custom loop, and then adjusted the arguments with pre_get_posts.
The strange thing was that, to test if it was this issue, running a custom loop on an archive page was the issue, I removed the archive page, and made a normal page with the custom loop, and I had the same issue.
I’m not sure how the above happened, I was probably just doing something else wrong.
Nevertheless, pagination is working now on my archive page, with the altered main loop.