Cleon
Legend
The Brecht priests' claim it's extraplanar in original seems unlikely on the face of it, although I suppose it could be a Fiendish/Half-Fiend/Water-Element Kraken that used to live in the Abyss or the Elemental Plane of Water. That could give it the SR of this monster, but might add more SLAs the original text makes no mention of!
Upon reflection, how about making it a Native Outsider?
Our only Awnshegh conversion is the Ice Fiend, which we decided was a Large Outsider (Chaotic, Cold, Evil, Native). Remember the Ice Fiend was human before gaining his Azrai Blood Powers.
If we follow that precedent for The Kraken it'd mean Colossal Outsider (Chaotic, Evil, Native, Water) for the Type (Subtypes).
Dang it, just noticed some stat issues in The Ice Fiend. Better raise them in "corrections".