Example Method:

GameLoop:

if PlayerEnters New World Event
Unload Unseen/Not Using Data In Arrays (Small stuff like unseen meshes/untriggered entities/etc)
Create New Thread (Load XML/Textures)
Create New Thread (Load 3D Models/Sounds)

If Threads Done And Player is distance away from old world X.
Unload old world data completely.

If Player walks back to old world.
Safe Stop Threads If Running.
Unload the new world
Create New Thread (Load XML/Textures)
Create New Thread (Load 3D Models/Sounds)


Draw World

End of GameLoop

If you only add data to your arrays/pointers/vectors after you remove the stuff not in use, what have you. You drastically lose the chances of a crash of calling a outbound element and can still to continue to call models/entities in your game loop if the player decides to walk back even and takes less time to kind of reload the last level. I would create a second variable for the arrays something like size_t safeSize for determine what entities or models are safe to call. Then just add or subtract it when you add remove entities completely in a second thread. Debugging threads are a pain and I would write you a script if I could, but the chances are of it working are 50/50 if your using Win32. The best thing to do when using threads is simply experiment experiment experiment and debug till you know you got something completely uncrashable. Setting thread as a high priority fyi usually when adding a resource is helpful since it doesn't mess things up to other functions making a call to your pointers/vectors from what I experienced using threads.

It seems this asynchronous file I/O isn't the solution though - one level worth of data is roughly 20 Mb, which is read from disk very quickly. The code that's eating up cycles appears to be parsing XML and texture data for the objects and materials.

Ignoring threading for the moment, if you want to optimize load-times, you've got to eliminate as much on-load/parsing logic as possible. It's definitely possible to *not* parse textures or XML files on-load - you can move this logic into a data-compiler tool, which you run once at compile-time, instead of once every run.
E.g. you're parsing textual XML into some kind of binary structure in RAM, you can do this at build time, and then save that binary structure to disk. At runtime of your game, you can then load the binary file directly, with no parsing required. This should make loading your level near instantaneous.

You can also have your engine do this at runtime and cache the results. In this case the first load will be slow, and any subsequent loads will be much faster. Of course you can ship your game with the binary versions so the user doesn't have to wait a long time on first load, but also make it easier to do modifications with the human-readable representation without having to run a separate compiler tool.

You could also make it so the engine keeps a fingerprint of the "readable" version that is currently compiled, and check against it upon initialization: if the hash has changed, go through the compilation process (hashing should be instantaneous unless your readable files are ludicrously large). Bonus points if you include both the readable and compiled version in the hash calculation, to ensure consistency.

This way people can mod the readable version easily and the engine will pick up on it, and they can also back up old compiled versions + the corresponding fingerprints for when they wish to revert and the engine won't try to recompile things that have already been.

Keep in mind that that the engine/game runtimes only make up half of an engine; the tool-chain is the other half (and the third half is documentation, support, bindings, etc ).
Yep, for example - if users had to manually run XML files through some command line app to generate game-usable files, then your runtimes are probably very efficient, but now your tool-chain is now not very friendly.
I've used about 6 different engines over the past 6 years, and they've all had some kind of automated data-compilation pipeline, but have implemented them in a few different ways:
1) The runtime generated cache. During development, when the run-times load a file, they first check in a 'cache' directory for a binary version of the file. If a valid cached version isn't found, the original is loaded and compiled, then saved in the cache directory. When shipping the final optimised (non dev) version of the game, the compilation code is #ifdef'ed out and only the cached files are archived. If you want to support modding, you can also ship the dev build.
2) The build system. Just like you do for your code, you create a type of "makefile" for your assets, often for a custom built build-system, but possibly also for an off-the-shelf one (e.g. XNA uses msbuild). Whenever you've updated some assets (e.g. saved/edited them, or updated SVN, etc) you run your build-script, which uses timestamps/hashes etc to only recompile the necessary files. The game doesn't contain any parsing/compilation code (just simple binary loading code); all the parsing/compilation code is pulled out into separate tools that are used by the build system.If you want to support modding, you can also ship the build system.
3) The persistent build system. As above, but the build system sits in your system tray all day and watches your source asset directory. Whenever you change a file, it automatically recompiles it in the background. If the game is running, then when it's complete, it sends the game a message telling it to reload the modified file.

Back to threading though -- if you do want to parse/compile raw assets at compile time, then it should be fairly easy to parallelize. The inputs are the raw file and the outputs are the binary file, besides that, it's an isolated process, which is great for threading. When the async load of the original file is done, you can send a message to a worker thread (possibly by pushing it into a thread-safe queue) containing the original file's buffer, and have the worker-thread send back a buffer containing the binary file when it's done. The main thread can poll for completion once a frame, while it renders the loading screen.