Short Answer: He was breaking a few eggs to make an omelet.
Once Paul and the Fremen had control of Arrakis, Paul took steps to confirm that he had the universe by the short 'n' curlies from two different angles:
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.
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.
Once he had a firm grip on the big chair, he then began enacting his plans on a grand scale. Spoilers, though, in case you haven't gotten this far yet:
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.
The Jihad - Paul's "Holy War" - had a single goal, which only a select few individuals were aware of:
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.
Paul's Jihad was the first major step of this plan. To answer your question more directly,
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.
There were other phases to the whole thing, but you'll need to keep reading to find out what they are. The books can get a little wordy and hard to follow at times, but the above is essentially the overall story arc for the first five books.
As for HOW the Fremen did this, it is often stated in the books that the Fremen army - especially once trained with the Atreides' "Weirding Way" - was, quite simply, the most effective fighting force the universe had ever seen. Paul had the deadliest army in history, the means to move them anywhere (via his control of the Spacing Guild), and a mission to use them for (prepare humanity for The Golden Path). It took them over a decade, but they eventually conquered every known world - even worlds that previously didn't answer to the Emperor Corrino. The religious aspect of the war made him not only a tyrant, but a malevolent God who must be worshipped or else.
Paul hated what he had to become, but felt he had no other options because of the reasons above. It was not something the Fremen had "forced" on him so much as he had regrettably allowed (and even encouraged) for these reasons.
EDIT: You may want to see the following question as well. It has many good answers that expand on The Golden Path and why it was needed in the long-term.
In Dune, was the Golden Path really necessary?
UPDATE: Just noticed the question at the end about the major houses. As part of the Jihad, the major houses were essentially reduced to fiefdoms or destroyed outright. The other major players like the Ix and the Bene Gesserit saw which way the wind was blowing and quickly tried to ally themselves or curry favor with Paul. Several of them were allowed to exist as long as they remained useful, and the main ones (Ix, Tleilaxu, Bene Gesserit) still existed in some form millennia afterwards.