A few thoughts, just floating around:
A good parallel in real life could be like North Korea, where the citizenry are told that the state will provide for them, but where basic food necessities simply aren't being met. For a time, the government can hang on by carefully targeting a power base. Control of information and resources is the main support of this sort of regime.
So for Zhakata:
Pre-industrial societies tend to funnel significant resources to the military class, even if it's a heavy burden, in a way that they might be less willing to do if it's just a civilian leader. Survival in harsh situations is more important in the short run. Zhakata may be sold as a deity locked in physical struggle against evil or chaos or entropy.
If you go with the Zhakata-as-law trope, then the Mongrelmen (representing chaos and decay) might be characterized as "servants of chaos", or perhaps just "those abandoned by Zhakata". Even the slow deterioration of arable lands could be a potent sign of creeping, consuming entropy at the vestiges of civilization.
Eating and consumption often take on religious symbolism, so we have fertile ground here for a creation myth if one is needed. Christ is consumed in bread and wine by Christians. Kronos ate his children to remain ruler of the gods. Persephone ate a few pips of the pomegranate, and hence the seasons. Numerous civilizations ate body parts and organs specifically to gain special powers by association. For Zhakata, food could be simply a tribute to lend strength to his struggle against the cold and dark.
Or, food could be a last linkage to tie him to the world of men - the reasoning being that if he leaves the mortal realm entirely, then we would lose his protection and face the wild darkness alone. If we stop feeding Zhakata our food, he ascends away from us and abandons us. The benefit of this interpretation is that Zhakata could be theologically held to be "above the fray". He's not locked in some desperate struggle against a Manichean dualistic foe - rather, he's an indifferent higher power who could casually leave us to our fates.
In this interpretation, the crush of popular opinion could quite easily compel obedience. Rather than the priests policing the tithes of food, they could merely spread the word that anybody who insults Zhakata by withholding food puts the entire mortal realm at risk. The rest of the faithful masses would police themselves and ensure compliance.
These doctrines are fairly bleak, and effectively amount to "the universe is out to kill us all, and Zhakata basically doesn't care but will help us if bribed". But at least it doesn't fall prey to the theological contradictions of a benevolent god responsible for mankind's misery. Given G'henna's scarce resources and the relatively factual evidence of Yagno's powers, I'd imagine that this regime would be fairly secure. The poverty of the terrain probably masks any further inefficiencies of the Yagno administration, and so rebels have a hard argument to make that they'd be able to "run things better". And even the most rational atheist might find it hard to argue against Yagno's spellcasting and mongrelmen magic.