How long does it take to migrate users from Exchange 2010 to the Exchange 2016 environment?
Its hard to say. It all depends on the size of the mailbox and how many sub-folders the mailbox has.
Just like any other internal migration? No cost too?
Correct. There is no extra charge for this migration.
Great. Have you heard any issues with Exchange 2010 users being unable to search messages that far with iPhone devices?
And do you think upgrading to 2016 is a good possible solution to this?
I haven't heard of any issues with that. Both servers do the same for activesync. I know that with exchange mailboxes on the phone you can set how far back it syncs but the user should still be able to do a search for a message past that time frame.
Migration from Exchange 2010 to Exchange 2016 depends on the size of the mailboxes and the number of mailboxes.