The other thing I was going to say last night, but was too tired to remember, was that you can do some simple experiments.

First, make a copy of your program without any database calls and run it. It should run in a matter of minutes. That will confirm whether it is really the database part that is slowing things down.

Another quick experiment is to create a database without indexes, and create a version of your program that does only INSERTs, no SELECTs or UPDATEs. If this runs fast, then you should go ahead and use my sort suggestion, above.

Besides the sorting idea, there are some MySQL-specific things you can look into. There's a (non-standard) REPLACE statement that I think you can use instead of using SELECT followed by UPDATE or INSERT.

Depending on version, there is also a LOAD DATA INFILE statement.