So in the Denebrum section of Occult Realms, there are several mentions of Neothelids and Neothelid Overlords with class levels. Now by my understanding, a monster’s CR generally goes up by 1 for each class level added to it, so would that make something like Premblikang—a Neothelid Overlord with 16 Cleric levels—have a CR of 36? That seems absurdly high, the only other thing that kind of a CR is the Oinodaemon. I’d really like some clarification on this, because even 1/2 CR each level for a total of 28 still seems unusually high. Another thing, the scale on the Denebrum map seems way off; Ilvarandin is about the same width as Denebrum on the Darklands map, but Ilvarandin’s 80mile scale is longer than Denebrum’s 200mile scale. No offence to the author or Paizo—maybe I’m missing something—but it makes me think the person who wrote that part of the book had no idea what they were doing.
Neothelids are a combat role monster. Cleric levels up through the original CR only increase the creature's CR by half the number of levels when following the monster advancement guidelines. Of course, they're only guidelines--use the Monster Statistics by CR table and your own judgment to adjust if the result's level of challenge seems higher or lower than that produced by the guideline. Complicating things is that the game math rather breaks down when you get that high-powered.
Rest assured, though, that sixteen cleric levels on an already CR 20 monster are no joke. The first level adds the "monster with class levels" modifiers to its ability scores. Sixteen levels give it four ability score boosts. Its base attack bonus increases from +24 to +36. It gets eight more feats. It gets 8th-level cleric spells to go with that now-souped-up Wisdom score. Its wealth increases dramatically, possibly giving it access to top-tier magic items, wishes, or other danger boosts that normally cost inordinate amounts of gold. And at that tier of game, you could easily be looking at something capable of creating multiple major artifacts.
Frankly, I'm surprised that it would worship anything at that point, even Yog. There are creatures that underwent apotheosis at a much lower CR than Premblikang.
CR is more an art than a science. Very much so when you get up to the higher tiers like that. Especially if that monster pre-buffed with the numerous all-day boosts a 16th level cleric could get it would be a terrible force to be reckoned with.
But if you just slapped the stat increases on it, picked a bunch of feats that didn't add a huge amount to its combat ability and had it occasionally cast a spell instead of attacking it wouldn't be "that" much harder than its default stat block.
CR is more an art than a science.
CR tends to be very easy to judge at low levels, where you can simply compare a monster's stats to guideline tables. At high levels abilities start to matter a lot more than raw numbers, so it becomes increasingly subjective. A Neolithid Cleric 16 is so far outside of the boundaries the CR guidelines were meant for that it's basically just a technical way to assign an XP value and cannot truly measure the danger level (which, to be clear, is extreme in this case).