Resposta curta: Ele estava quebrando alguns ovos para fazer uma omelete.
Long Answer:
Uma vez que Paul e os Fremen tivessem o controle de Arrakis, Paul tomou medidas para confirmar que ele tinha o universo pelos curlies curtos de dois ângulos diferentes:
Economicamente,
Paul had the ability to destroy the spice. During the war on Arrakis, Paul had the Fremen plant "water-bombs" under all the major spice caches. With the touch of a button, Paul could destroy the economy of the entire universe in one fell swoop. This ensured that most of the major Houses would not attempt to seize power back using violence.
Politicamente,
Paul took Princess Irulan as his "official" wife and thus became Emperor by marriage. This ensured that the major Houses could not overthrow him using political or legal means.
Uma vez que ele tinha um aperto firme na cadeira grande, ele então começou a encenar seus planos em grande escala. Spoilers, no entanto, caso você não tenha chegado tão longe ainda:
Both Paul and his offspring could see the full range of time - all possible timelines save for one led to the eventual stagnation, decline, and extinction of humanity. The ONE timeline that led to humanity's eternal survival as a race required Paul (or one of his descendants) to take "The Golden Path". Essentially, the only way for humanity to survive long-term was to make them scatter to the four corners of the universe.
A Jihad - a "Guerra Santa" de Paulo - tinha um único objetivo, do qual apenas alguns poucos indivíduos sabiam:
to make humanity so sick of despotism that they would literally flee to all corners of the galaxy to get away from it. The Golden Path required humanity to first become like a coiled spring that would later explode, ejecting humanity to every square inch of the universe in such numbers that they could never be endangered again as a species.
A Jihad de Paulo foi o primeiro grande passo deste plano. Para responder à sua pergunta mais diretamente,
Yes, killing 61 billion humans was an evil and inhumane thing, but compared to Paul's knowledge of what was coming it was but a drop in the bucket. He was doing it to save humanity as a whole in the long run.
Havia outras fases para a coisa toda, mas você precisa continuar lendo para descobrir o que elas são. Os livros podem ser um pouco trabalhosos e difíceis de seguir às vezes, mas o acima é essencialmente o arco geral da história para os primeiros cinco livros.
Quanto a COMO os Fremen fizeram isso, é frequentemente declarado nos livros que o exército Fremen - especialmente uma vez treinado com o "Caminho do Barulho" dos Atreides - era, simplesmente, a força de combate mais efetiva que o universo já havia visto . Paulo tinha o exército mais mortal da história, os meios para movê-los para qualquer lugar (através de seu controle da Corporação Espacial) e uma missão para usá-los (preparar a humanidade para o Caminho Dourado). Eles levaram mais de uma década, mas acabaram conquistando todos os mundos conhecidos - mesmo mundos que antes não respondiam ao imperador Corrino. O aspecto religioso da guerra fez dele não apenas um tirano, mas um Deus malévolo que deve ser adorado ou então.Paul odiava o que ele tinha que se tornar, mas sentiu que não tinha outras opções por causa das razões acima. Não era algo que os Fremen tivessem "obrigado" a ele tanto quanto lamentava (e até encorajava) por essas razões.
EDITAR: Você pode querer ver a seguinte pergunta também. Tem muitas boas respostas que expandem o Caminho Dourado e por que isso foi necessário a longo prazo.
Na Duna, foi o Caminho Dourado realmente necessário?
ATUALIZAÇÃO: Apenas notei a questão no final sobre as principais casas. Como parte do Jihad, as casas principais foram essencialmente reduzidas a feudos ou destruídas de imediato. Os outros grandes jogadores, como o Ix e a Bene Gesserit, viram de que lado o vento estava soprando e rapidamente tentaram se aliar a eles ou agradar Paul. Vários deles foram autorizados a existir enquanto permaneceram úteis, e os principais (Ix, Tleilaxu, Bene Gesserit) ainda existiam em alguma forma milênios depois.