Hi,
if these two functions work when the DB is smaller, but fail after a certain size, then you are hitting a limitation with string functions most likely. PHP restricts the size of strings in certain functions, as well as hits a limit with indexes into huge arrays.
I would modify these functions to read a number of entries at a time from the DB in a 'while' loop. That would keep the strings and indexes within the permitted ranges, whilst also allowing the function to complete its task.
With regards to speed for handling a few million URL's, then that may be something which is limited by factors outside a developer's control, such as the hardware you are using, processes you are running on your server etc.
BR,
Will