https://pl.wiktionary.org/wiki/powinien

The word powinien is a former adjective that assumed the role of a verb hundreds years ago, and it merged with być, therefore it takes the same ending as jest. It's the one of two Polish defective verbs that conjugate by persons (the other is winien and it's a less popular synonym of powinien – don't confuse it with an ordinary adjective winien/winny), and there are no words other than those two that follow this pattern.

masculine:
powinienem
powinieneś
powinien

feminine:
powinnam
powinnaś
powinna

neuter:
powinno

masculine personal plural:
powinniśmy
powinniście
*powinni

non-masculine-personal plural:
powinnyśmy
powinnyście
*powinny

Past tense (althought you can use the previous forms to refer to the past as well):

masculine:
powinienem był
powinieneś był
powinien był

feminine:
powinnam była
powinnaś była
powinna była

etc.

Conditional mood (rarely used):

masculine:
powinien bym
powinien byś
powinien by

feminine:
powinna bym
powinna byś
powinna by

etc.

There's no future tense or any other forms.

Hi, I do not know formal rules, but as a native speaker I can give you small hint: "powinieneś" (should) is related with word "powinność" - duty.

My guess would be that it evolved into „ś” because of preceding syllable being soft. It just sounds strange to me going from soft „ni” to „sz” at the end.

No, it's good now. Sometimes the negative meanings of some words might not make intuitive sense for somebody coming from a different language. In Poland for example people learning English might at first be surprised with the meaning of "musn't", which they might expect to be closer in meaning to "don't have to".

Both of what?