I'm fairly far along developing a Kivy app. Its targeted for android, but will also work (simultaneously with a different skin) on desktops and hopefully iOs eventually.
The basic dependencies I'm heavily using are:-

twisted - using this as an IPC, my app has a server/client
relationship   between the data manipulation and the UI
Whoosh - for text search
xmltodict - for easy XML manipulation

I'm having REALLY long app startup times on android, on a relatively recent phone, which doesn't bode well. From my rough timings (based on time.time() and subtracting from my App's init time):-

My app gets control from kivy startup at about 1 second in
My initialization of custom classes etc. is done at the 2.4 second mark
At the 14.4 second mark, I finally complete the bulk of my data loading
At the 17 second mark, I start sending the data out to the client UI using twisted
At the 22 second mark, the UI receives the data

There's multiple points I want to address there. For example the roughly 5 second gap for data send can be easily broken into pieces and updated in the UI piecemeal, so I'm keeping that for later, but I need to ask about the long 12 second gap for data loading. This data loading involves creating about a 1000 instances of a custom class, with the following steps (cumulative time over 1000 instances):-

Reading data from 1000 text XML files (0.734 seconds)
Parsing the XML in the read data (9.198 seconds)
Filling the object's variables based on the parsed XML (0.585 seconds)
Directory tree traversal (use this to locate a certain base folder, 0.0824 seconds)
mtime measurement for the xml files (0.12 seconds)

The measured timings surprised me, because the equivalent timings for running the same code on my laptop are 0.041, 0.9, 0.062, 0.009, and 0.016). Everything's about 10 times slower.
What, if anything, can I do about this? The phone being used for testing has 3GB of RAM and a Snapdragon 801 processor, so I'm quite worried about using this app on slower/older models. My initial thoughts were that the slow-down was due to sd cards being inherently slower than my laptop's hard disk drive, but the fact that xml parsing (non IO related) took so long seems to indicate processing problems.
Suggestions/criticisms welcome.
The immediate possibility is that you're just seeing the android processor be slower than the desktop one. I'm not sure what the benchmark comparisons are nowadays, but I've seen this be a problem in the past. That said, I'd have guessed the same as you that the difference shouldn't be that big.
I don't know if it would make a difference, but one general thing to try might be to compile for armeabi-v7a (rather than the default armeabi). This enables hardware floating point calculation, amongst other things. I don't know if it makes a difference in generic apps, but it certainly could. You can target this using the python-for-android master branch with --arch=armeabi-v7a, or the android_new target in the buildozer master branch (the rest of buildozer operation is the same, and it automatically uses v7a).
Another question would be, do you have access to a more efficient xml parser? If you can find one in e.g. cython rather than python (I don't know what you're using right now), this could make a difference. I see the other alternative of using a more efficient data structure has already been raised in a comment.
Sorry that neither of these suggestions are very specific. If you ask on the kivy support channels you may find someone who's found and resolved similar issues.
Python on android (kivy) - speed bottlenecks for certain operations?