The Sahagin is somewhat agile, and it will use its Jump attack frequently. Make sure that Zack has Dualcast materia equipped. Start with Dualcasting Graviga on the Sahagin until its HP is below 99,999 points, then hit it hard with Costly Punch.
Jumping just after the enemy helps, too. It takes longer, but you take less damage.