On a PSP-1000 with M33 5.00 the only time I ever encountered lag in War of the Lions was when I used a CSO file - the spells chopped up pretty bad. Use an ISO (uncompressed) image and your problems will most likely go away. Also, if you're using a cheap memory stick the transfer rates sometimes affect game performance - try a different stick and see if the problem persists.
If you're using an emulator, however, I don't know what to tell you.