Autocomplete Migration from Exchange 2016 to Exchange Online

Yes, it is actually a folder inside the mailbox. 

Do we know which folder?

The autocomplete data is stored as IPM.Configuration.Autocomplete messages in the Associated Content Table of the inbox.

docs.microsoft.com/.../information-about-the-outlook-autocomplete-list

Do we migrate IPM.Configuration.Autocomplete as part of migration? 

I think we do. But I would have to test it to be sure.