PerlMonks is not a code-writing service.

The script you have is fine as it is (if it works), what you need is another script that first divides the job so that it becomes manageable. Keys that have differing beginnings can never match, therefore, partitioning the records by their start serves to effectively reduce the job into many smaller jobs.

What part of the suggestion are you struggling with? For starters, you could try to work out a script that reads the records and dumps them on the screen, together with a note "this record must go in that file". The problem you have is a good learning opportunity, as it can be readily broken down into smaller sub-tasks that a beginner can handle.