You are supposed to complete the game in under 80 minutes for this trophy, however...
I'm not sure if the timer is glitched (in your favor) or if maybe the cut scenes and finishing move cine-matics don't count in your time, because timing myself (with a stop watch), mine came to 85:19 when I defeated Underboss.
I did it with Nite Owl after I had all the abilities. I utilized the electric shock anytime there were BIG enemies around as they take the most time to defeat. I found that by throwing enemies (with circle) you were able to defeat them faster, because it only takes three hits with them on the ground and you can knock down groups of them by throwing one guy into the middle of the pack. If you are high up, throw enemies over rails or into water to save time. When you are separate paths, you often don't have to kill all enemies, just avoid them and move to the next section. However, if it is a section where you will be opening a door or grappling, you will usually have to kill them before you can move on.
On Underboss, DON'T worry about any of the enemies while you are chasing him. Until you battle him for the first time, the enemies won't really bother you if you just keep running. The first enemies you must kill are the big posse just after Underboss goes up a ladder, there are a bunch of them. Hopefully you've let your "charge" fill up because one burst with that and they all die and you can move on. Once you start battling him, you do have to clear all enemies before going up the ladder.