What variable(s) to look to maintain MySQL speed of scanning through all database tables while it starts?
SPEEDING UP SHUTDOWN / STARTUP
Since you are dealing with the InnoDB Storage Engine, you need to think about what MySQL does during a startup and during a shutdown.
During a shutdown, InnoDB tends to freeze everything in terms of transactions Dirty pages in the InnoDB Buffer Pool are flushed. During a startup, InnoDB crash recovery rolls forward any leftover changes in the transaction logs. The InnoDB Double Write Buffer may also be scanned during InnoDB crash recovery.
The first variable I think you should set innodb_fast_shutdown to 0.
Please note the MySQL Documentation:

The InnoDB shutdown mode. If the value is 0, InnoDB does a slow
shutdown, a full purge and an insert buffer merge before shutting
down. If the value is 1 (the default), InnoDB skips these operations
at shutdown, a process known as a fast shutdown. If the value is 2,
InnoDB flushes its logs and shuts down cold, as if MySQL had crashed;
no committed transactions are lost, but the crash recovery operation
makes the next startup take longer.
The slow shutdown can take minutes, or even hours in extreme cases
where substantial amounts of data are still buffered. Use the slow
shutdown technique before upgrading or downgrading between MySQL major
releases, so that all data files are fully prepared in case the
upgrade process updates the file format.
Use innodb_fast_shutdown=2 in emergency or troubleshooting situations,
to get the absolute fastest shutdown if data is at risk of corruption.

OK that takes care of a faster startup. The tradeoff is longer shutdown.
Is there anything you can do speed up a shutdown ? Yes !!!
Get dirty pages from the InnoDB Buffer Pool written to disk more frequently. How ?
You need to set innodb_max_dirty_pages_pct = 0. By doing this, the shutdown process takes less time to flush dirty pages to the .ibd files.
Is there anything else to help startup ? Yes, there is one more.
When you startup mysql, usually the InnoDB Buffer Pool is empty after its allocation.
You could make mysql save the block numbers of all 16KB pages that were in the the buffer pool. Just add innodb_buffer_pool_load_at_startup and innodb_buffer_pool_dump_at_shutdown. This will not time a long time since it writes block numbers to a binary files, not the blocks themselves.
LARGER NUMBER OF FILES
InnoDB's default for open files (innodb_open_files) is 300 for MySQL 5.5. For MySQL 5.6, the ideal number is set for you. You may need to increase this value as well. InnoDB may cache the open files once you reach this limit.
You may have to compensate by raising the value to 100000 or 200000. You could also increase the ULIMIT in the OS to allow MySQL to have more file handles and set open_files_limit to that max value.
I would further suggest increasing RAM in the DB Server.
SUMMARY
Here are the options you need to add
[mysqld]
innodb_fast_shutdown=0
innodb_max_dirty_pages_pct=0
innodb_buffer_pool_load_at_startup=1
innodb_buffer_pool_dump_at_shutdown=1
innodb_open_files=(much higher value)
open_files_limit=(much higher value)

Depending on the environment, you may not need all four options. Perhaps setting innodb_fast_shutdown to 2 is better than 0. Maybe the default setting for innodb_max_dirty_pages_pct is fine if you have low-write activity. In any case, test which options help your shutdown and startup concerns.
Keep in mind that innodb_buffer_pool_load_at_startup and innodb_buffer_pool_dump_at_shutdown are for MySQL 5.6. Therefore, check to see if the version of Percona Server you are using has those two options.
Give it a Try !!!