Will we be able to do the upgrade in October 2023 with our classic folders, and then only afterwards do the migration to modern folders, or do we have to do the migration before the upgrade?
I have to assume you are asking regarding an on premise solution, as the cloud version already has them deprecated and to be removed any time now if they aren’t already.
If you are on prem, you need to indeed upgrade before migration. Classic folders are no longer supported.
I’d suggest doing it immediately, there is no good reason to delay the work further.