I saved the Marks until all at the very end of the game so I was pretty high in levels when I beat him; I'm guessing around 55. I saved right before the first fight though because it's just such an awesome and memorable battle, right from the hilarious introduction to Gilgamesh.