My lists are around 5,000. Using external_choices is key.
One item that can get you is relevant. I have a form what loads this 5,000 item list 12 times per repeat! On Android it takes 2-4 seconds to load a repeat. iOS it is instant. What breaks is if I try to hide all 12 of these fields behind a relevant iOS will crash the app. Android will start randomly losing field calcs. This is esp true the more apps that are open on the tablet. So in the end I had to unhide 4 of the fields to get it to stop crashing.
The new 3.5 64 bit Android version does seem to make all of this better (both speed and memory management). The bummer for us is the rugged Samsung Active 2s we bought are still running 32 bit Android even though it is a 64 bit chip.
This all became a bigger issue when I tried to use repeat_count. I set it to 50 it seems to preload all 50 x 12 lists each = crash. Had to take the repeat_count back out.
Hope this helps.