Yeah, I'd probably start with Dagon, boost Dex a little and reduce Con a little. Maybe Str 36, Dex 16, Con 34?
Hmm, we could give Ythog a "maximum hp" ability like we did the Dense Pudding?
Hearty (Ex): When fully healed, a dense pudding always has the maximum number (10 + Con modifier) of hit points per HD.
As for the stats, we seem to be agreed
Fiendish Codex I Dagon's stats are in the right ballpark and could be used with a little tweaking.
Also consider the Fiendish Codex II stats for Baalzebul, the slug-bodied Arch-Devil whose physical form is very similar to Ythog-Nthlei.
[FONT="]Dagon, Prince of the Darkened Depths
[/FONT][FONT="]Fiendish Codex I[/FONT][FONT="]:[/FONT][FONT="] Gargantuan; CR 22; HD 25 (462 hp); AC 42, touch 7, flat-footed 41; SR 33; Abilities Str 36, Dex 12, Con 38, Int 22, Wis 25, Cha 16[/FONT]
[FONT="]Baalzebul, Lord of the Seventh [Arch-Devil]
[/FONT][FONT="]
Fiendish Codex II: Huge, CR 23; HD 30 (495 hp); AC 47, touch 9, flat-footed 46; SR 31; Abilities Str 39, Dex 13, Con 34, Int 28, Wis 27, Cha 25[/FONT]