Where does the power of a Jewish king to sentence to death come from?

Question

Rambam Melachim 3:8:

"כָּל הַמּוֹרֵד בְּמֶלֶךְ יִשְׂרָאֵל יֵשׁ לַמֶּלֶךְ רְשׁוּת לְהָרְגוֹ.
אֲפִלּוּ גָּזַר עַל אֶחָד מִשְּׁאָר הָעָם שֶׁיֵּלֵךְ לְמָקוֹם פְּלוֹנִי וְלֹא הָלַךְ אוֹ שֶׁלֹּא יָצָא מִבֵּיתוֹ וְיָצָא חַיָּב מִיתָה.
וְאִם רָצָה לְהָרְגוֹ יֵהָרֵג.
שֶׁנֶּאֱמַר (יהושע א יח) "כָּל־אִישׁ אֲשֶׁר־יַמְרֶה אֶת־פִּיךָ וְלֹא־יִשְׁמַע אֶת־דְּבָרֶיךָ לְכֹל אֲשֶׁר־תְּצַוֶּנּוּ יוּמָת רַק חֲזַק וֶאֱמָץ׃"

"The king has the right to execute anyone who rebels against a king."

The idea seems to be anonymously accepted in the Gemmorah, but I couldn't find any discussion on King's rights. Moreover, the Pasuk talks of Yehoshua that wasn't a king (officially) but he was a prophet, so the punishment can be seen as זקן ממרה - contradicting G-d's prophecy, and not as a King's will.

In Shmuel 8, Shmuel lists the 30 rights of the Jewish King:

"וַיֹּאמֶר זֶה יִהְיֶה מִשְׁפַּט הַמֶּלֶךְ אֲשֶׁר יִמְלֹךְ עֲלֵיכֶם:
אֶת־בְּנֵיכֶם יִקָּח וְשָׂם לוֹ בְּמֶרְכַּבְתּוֹ וּבְפָרָשָׁיו וְרָצוּ לִפְנֵי מֶרְכַּבְתּוֹ׃
וְלָשׂוּם לוֹ שָׂרֵי אֲלָפִים וְשָׂרֵי חֲמִשִּׁים וְלַחֲרֹשׁ חֲרִישׁוֹ
וְלִקְצֹר קְצִירוֹ וְלַעֲשׂוֹת כְּלֵי־מִלְחַמְתּוֹ וּכְלֵי רִכְבּוֹ׃
וְאֶת־בְּנוֹתֵיכֶם יִקָּח לְרַקָּחוֹת וּלְטַבָּחוֹת וּלְאֹפוֹת׃
וְאֶת־שְׂדוֹתֵיכֶם וְאֶת־כַּרְמֵיכֶם וְזֵיתֵיכֶם הַטּוֹבִים יִקָּח וְנָתַן לַעֲבָדָיו׃
וְזַרְעֵיכֶם וְכַרְמֵיכֶם יַעְשֹׂר וְנָתַן לְסָרִיסָיו וְלַעֲבָדָיו׃
וְאֶת־עַבְדֵיכֶם וְאֶת־שִׁפְחוֹתֵיכֶם וְאֶת־בַּחוּרֵיכֶם הַטּוֹבִים
וְאֶת־חֲמוֹרֵיכֶם יִקָּח וְעָשָׂה לִמְלַאכְתּוֹ׃
צֹאנְכֶם יַעְשֹׂר וְאַתֶּם תִּהְיוּ־לוֹ לַעֲבָדִים׃"

But I can't spot the right to sentence to death. It is also very counterintuitive (in our times) to place a King's whims before G-d's justice.

So Where is this power learned from?

Answer 1

As to your point about Yehoshua not being a(n official) king, see your question about this and the answers thereto which provide sources stating that Yehoshua was a king. Also note that in his commentary to the statement of Rambam that you cited here, R. David Ibn Zimra writes that a king for these purposes does not have to be officially appointed. As long as all of Israel accepts him, he has the status of a king:

והאי מלך היינו שהומלך על פי נביא או שהסכימו עליו כל ישראל אבל אם קם איש אחד ומלך על ישראל בחזקה אין ישראל חייבין לשמוע אליו והממרה את פיו לא נקרא מורד במלכות

As to why the ability to put rebels to death is not mentioned in Shmuel's list of the king's powers, I would suggest that it is because this ability is fundamentally different from the others mentioned. The other things mentioned there are things that the king can do to the commoners that the commoners have no control over. Shmuel is warning them that having a king will be unpleasant because a king can seize their property and family for his own interests. But the death penalty under discussion here is not something that the king can just inflict on the people. It is a specific punishment for a specific crime. If a citizen rebels against the king then the king has the right to kill the citizen. But if the citizen does not rebel then the king cannot kill the citizen. So it's not something that is subject to "abuse" in the same way; the citizens can just not rebel against the king's orders and then the king will not have the right to kill them.