By your argument, they should never have made any effort that did not lead directly to increasing their power.
But their rule wasn't (just) a goal in itself, but a tool used to achieve other goals. Given that they had a chance of failing to achieve lasting world domination, it made sense to pursue goals like killing Jews which would leave a lasting legacy even if they were ultimately defeated. In other words, the destruction of the Nazi regime is not the absolute possible min-utility.
Besides all of that could have been achieved by taking away power from all jews and putting them in ghettos. Which they had already done before even starting on the "final solution".
If the ghetto solution had worked, they would not have needed the Final Solution, and would not have worked on it. The F.S. wasn't just for the fun of it - it was created to handle the problem of large jewish populations in newly-conquered Eastern territories. In some of these territories they never instituted ghettos because killing the jews right away was thought to be economically cheaper or more efficient (e.g. Ukraine). In others (Poland, etc), they thought that ghettos wouldn't work in the long term, and they had or feared local management problems. It's easier to kill a hostile conquered population than to keep it from revolting while it starves. (They also had plans to kill most of the Poles, but they never had the manpower to carry those out.)
Later, towards the end of the war, it acquired an additional (rational) reason: killing all the jews quickly before the relevant territories were lost to the advancing Red Army.
By your argument, they should never have made any effort that did not lead directly to increasing their power.
There are at least two 'increasing their power'. One is individuals gaining power in Germany. That was a subgoal. The other is increasing the power of their nation or race in the world. That is the supergoal that, according to their ideology, all nazis should be working for. Beyond that they could have personal selfish goals. Perhaps including survival, reproduction and a legacy of having achieved something constructive. All of which they failed...
As Eliezer and many others on Less Wrong have said, the way the human species rose to dominate the Earth was through our intelligence- and not through our muscle power, biochemical weapons, or superior resistance to environmental hazards. Given our overwhelming power over other species, and the fact that many former top predators are now extinct or endangered, we should readily accept that general intelligence is a game-changing power on the species level.
Similarly, one of the key ingredients in the birth of the modern era was the discovery of science, and its counterpart, the discovery of the art of Traditional Rationality. Armed with these, the nations of Western Europe managed to dominate the entire rest of the world, even though, when they began their explorations in the 15th century, the Chinese were more advanced in many respects. Given how Western Europe, and the cultures derived from it, has so completely surpassed the rest of the world in terms of wealth and military might, we should readily accept that science and rationality is a game-changing power on the civilization level.
However, neither of these imply that intelligence, science, and rationality, as a practical matter, are the best way to get things done by individual people operating in the year 2009. We can easily see that many things which work on the species level, or the civilization level, do not work for individuals and small groups. For instance, until the discovery of nuclear weapons, armed conflict was often a primary means of settling disputes between nation-states. However, if you tried to settle your dispute with your neighbor, or your company's dispute with its competitor, using armed force, it would achieve nothing except getting you thrown in prison.
People are crazy and the world is mad, but it does not necessarily follow that we should try to solve our own problems primarily by becoming more sane. Plenty of people achieve many of their goals despite being completely nuts. Adolf Hitler, for example, achieved a large fraction of his (extremely ambitious!) goals, despite having numerous beliefs that most of us would recognize as making no sense whatsoever.
We know, as a matter of historical fact, that Adolf Hitler and his Nazi Party, despite being generally incompetent, unintelligent, irrational, superstitious and just plain insane, managed to take over a country of tens of millions of people from nothing, in the span of fifteen years. So far as I am aware, no group of people has managed to achieve anything even remotely similar using, not only rationality, but any skill involving deliberative thought, as opposed to skills such as yelling at huge crowds of people. However, it is a corollary to the statement that no one knows what science doesn't know that no one knows what history doesn't know, so it is entirely possible, perhaps likely, that there is something I am overlooking. To anyone who would assert that intelligence, science or rationality is the Ultimate Power, not just on the level of a species or civilization, but on the level of an individual or small group, let them show that their belief is based in reality.