In any optimisation task the first step is to profile the code. I guess that you have not yet done this (otherwise why would you not have shared the results with us).
Fortunately perl has a plethora of profiling options. The first port of call is the recommended Devel::NYTProf. Alternatively you could try the minimalist Devel::FastProf.
Once you've profiled it you will be in a better position to know where the problem lies.
In the meantime I would suggest breaking out your big nest of if/elses into separate subroutines for ease of both profiling and general maintenance.