In the game the sword is your only weapon. You will easily encounter far more than 500 enemies. So if you don't skip them, you will have this trophy unlocked probably around just before going to the Ruins of Rekem. If by some reason you don't get this during your normal playthrough, you can just continue the counter by using the challenges or by playing new game plus (hit new game instead of continue).