I have a bookmark file with somewhere between 500 and 600 items in it, about 50 of which are in folders.
If the bookmark toolbar is enabled, it takes on the order of 8-10 seconds to open a new browser window. This happens whether or not the bookmark toolbar is actually enabled, and regardless of how the window is opened. Traces from the Windows Task Manager indicate that the CPU load is 100% during the delay.
If I disable the bookmark toolbar and restart K-Meleon, new windows open in less than a second.
(Note that this is on a Pentium-Pro 200Mhz machine; one would not expect this to be a noteworthy problem on significantly faster computers.)