Short Answer:
The long answer below will include actual historical examples of titles including two or more different words meaning emperor.
Possibly the title of padishah emperor was short for a long and complicated full title. The long answer will also include some historical examples of long and Complicated full titles.
Or possibly he was called the padishah emperor to distinguish him from earlier padishahs in history who were not emperors, or to distinguish him from earlier emperors who were not padishahs.
There have been many persons in Earth up to the present time who were more less either padishahs or emperors or both, And I believe there was supposed to be about ten thousand years of future history before the foundation of the Empire in Dune, which in turn was about ten thousand years before the novel.
So that is a lot of history and possibly a lot of padishahs and a lot of emperors before someone decided to claim to be both padishah and emperor.
Another possibility is that the ruler is always "reallY" called padishah by the characters in Dune, and Frank Herbert sometimes writes it as padishah, and sometimes as emperor, and sometimes as padishah emperor, to let the readers know that mentions of the padishah and the emperor refer to the same man.
I note that in the Mughal empire, padishah became badshah, which any English enemies of the Mughals might have considered appropriate. With that as one example, we can only speculate how much languages and words might change in twenty thousand years until the era of Dune,
So maybe in Dune the monarch's title is "really" dormo irmcid or ikecith n'ficimcn or something, which Herbert translated into modern English more or less arbitrarily as padishah empeor.
Long Answer.
A Discussion of Imperial Titles.
In my opinion the only emperors were emperors of a Roman Empire. If a realm is not a Roman Empire, its ruler cannot be an Emperor. Every Roman Emperor claimed to be the rightful ruller of the world or the universe.
So I consider the so-called "Emperors" who ruled specific lands and peoples in societies with European or European influenced cultures, From the "Russian Empire" founded in 1721 to the "Central African Empire" in 1976-1979, to be merely "inferators" instead of imperators, and I think that their realms were merely "inferiums" instead of imperiums.
And I do not count the various European colonial realms as "empires" either, regardless of the titles used by their heads of state. Instead they could be called something like "colonial unions" or Thalassocracies - sea realms.
And there have been a number of non European societies which could be considered to be "empire equivalents", and whose rulers could be considerd to be "emperor equivalents".
Among the realms which might be considered empire equivalents are the Inca Empire, the Caliphate of Islam, the Persian Empire, The Mongol Empire, the Mughal Empire in India, the Chinese Empire, etc. Their rulers used titles like Sapa Inka (only lord), Khalifa ("Successor" of the Prophet Mohammed), ShahanShan (King of Kings), Yekhe Khagan (Great khagan, which is much higher than the mere "Great Khan" it is often translated as), Padishah (Master King), and Huangdi.
And of course some people would add or subtract various states from this list of possible empire equivalents.
Many people have the opinion that a king of kings is equal to an Emperor, But even though the Persian emperor equivalents used the title of king of kings, very few other users of the title of king of kings counted as emperor equivalents.
Imagine a galactic empire whose emperor rules the entire Milky Way Galaxy. Imagine that it has a feudal hierarchy. How many levels of subordinate feudal rulers will there be a galactic empire?
In Habitable Planets for Man, Stephen H. Dole, 1964, the properties of planets habitable for humans were discussed.
https://www.rand.org/content/dam/rand/pubs/commercial_books/2007/RAND_CB179-1.pdf
On pages 101 to 105 Dole discussed the probability that a specific star would have a habitable planet in orbit. And on page 103 Dole estimated that there were about 600 million (600,000,000) human habitable planets in the Milky Way Galaxy.
In the decades since then many scientific discoveries and caclulations have been made which in some cases would lower the estimated number of human habitable planets and in other cases would raise them.
But modern astronomers mostly discuss the possibilities of planets habitable for lifeforms using liquid water in general, without specifying which percentage of those planets would be habitable for humans in particular.
Modern estimates that there are various multiples of billions of planets habitable for liquid water using lifeforms in general in the Milky Way Galaxy certainly imply that there are various multiples of millions of planets habitable fo humans in particular in the Milky Way Galaxy.
And it is now believed that almost everystar system in the Mikly Way Galaxy has various numbers of planets, moons, asteroids,comets, etc. which can be mined for materials to make enclosed planetary colonies and artifical space habitats. So even a star system with no habitable planet could be colonized and eventually have a population of billions, trillions, or quadrillions of humans.
And there are estimated to be about 100 to 400 billion (100,000,000,000 to 400,000,000,000) star systems in the Mikly Way Galaxy.
So try to imagine a feudal hierarchy in a hypothetical galactic Empire. Suppose that each solar system is ruled by a king- elected from below, hereditary, or appointed from above. If there was only one king or queen in every solar system royalty would be many times rarer than on Earth at the present.
Suppose that the ruler of 10 star systems was a king of kings, or king to the 2nd pwoer, or K2, and the ruler of 100 star systems was a King of kings of Kings, or K3, and the ruler of 1,000 star systems was a King of kings of kings of Kings or K4, and so on. Obviously the galactic Emperor would be several levels higher than a mere king of kings.
So I don't think very highly about stories about fictional space empires where the highest ranking vassels of the space emperor are mere dukes. Space emperors should have kings, and kings of kings, and kings of kings of kings, and so on, below them.
And of course the entire universe, which a real space empire would claim to be the rightful government of, is incredibly, unbelievably, fantastically many times vaster than our incredibly vast but comparatively tiny Milky Way Galaxy.
And some people might says that this is all theoretical and hypothetical.
But my answer to:
https://worldbuilding.stackexchange.com/questions/110223/imperial-kingdoms
has a number of examples of kings of kings who were subordinate to higher rulers, including emperors.
So I say that only the Persian kings of kings, and maybe a few others, were emperor equivalents, and most historical kings of kings were much lower than emperors or emperor equivalents, a number being actual clients, tributates, and vassels of emperors or emperor equivalents.
The USe of Multiple Titles by Emperors.
As for imperial titles, the early Roman emperors were more or less military dictators who controlled the Roman Republic, but who pretended to be merely very influentual senators. That didn't exactly fool anyone, but it was sort of a courtesy to the other senators, not flaunting the imperial power too much for the senators to bear and thus - the emperors hoped - not forcing the proud senators to avenge that insult to their pride by overthrowing the emperor.
So the early Roman Emperors accumulated a number of Republican powers, titles, and jobs, to provide constitutional justification for the orders they gave and decisions they made. And they did not have a single title, since that would make their absolute rule too obvious.
So the Roman Emperors used a bunch of different titles, such as Princeps, Imperator, Caesar, Augustus, Pontifex Maximus, Dominus, Pater Patriae, etc.
The heir to the throne, or a junior emperor, often used the title of Imperator Caesar, while a full or senior emperor used the title of Imperator Caesar Augustus. The usual format in inscriptions, etc. went "Imperator Caesar - insert full name here - Augusutus". Thus one might claim that the tile of a Roman Emperor in the classical era was a three word phrase Imperator Caesar Augustus instead of a single word.
Or one might claim that each of the three words meant emperor separately, and that the usual form was "emperor, emperor - insert name here- emperor".
Anyway, that is one historical precedent for the use of a title resembling padishah emperor.
In 800 Charlemagne claimed that the imperial throne had been vacent since Constantine VI was overthrown in 797, and so had himself crowned emperor in Rome.
In his official charters, Charles preferred the style Karolus serenissimus Augustus a Deo coronatus magnus pacificus imperator Romanum gubernans imperium[109] ("Charles, most serene Augustus crowned by God, the great, peaceful emperor ruling the Roman empire") to the more direct Imperator Romanorum ("Emperor of the Romans").
Since augustus and imperator were either two parts of the imperial title or two separate imperial titles, opinions may vary whether Carlemagne called himself emperor once or twice in that title. But Charlemagne certainly used two different words that were often used to mean emperor in his title.
So that is a historical precedent for the euse of a title resembling padishah emperor.
The later Carolingian emperors, and the early emperors of the Holy Roman Empire, usually used the title imperator augustus. That can be interpreted as a two world phrase meaning "emperor",or as a phrase with two separate words each meaning "emperor", and thus meaning "emperor emperor".
So that is a historical precedent for the use of a title resembling padishah emperor.
By about 1200, the person elected future emperor used the title of Rex Romanorum et semper Augustus until and unles they were crowned emperor by the pope in Rome, and then used the title of Imperator Romanorum et semper Augustus.
Some sources translate semper Augustus as "always august". But I don't know whether the Latin word Augustus can be used as an adjective as well as a noun.
To me it makes more sense to translate the titles as "King of the Romans and always
Emperor" and as "Emperor of the Romans and always Emperor". That would be intended to show that the King of the Romans was already emperor with full imperial rights and powers from the time of their election and coronation as king of the Romans, and that the coronation in Rome merely caused a relatively minor change in their title.
So if I ever revive the Holy Roman Empire, I will certainly demand that semper Augustus should be translated into English as "always emperor" and not as "always august".
Anyway, Imperator Romanorum et semper Augustus contains two different words used for emperor, and so counts as a precedent for padishah emperor.
Later emperors listed their various titles of the lordships, countships. landgravates, amargravates, principalities, duchies, kingdoms, etc. that they ruled or claimed as hereditary possessions, as well as their titles as elected emperors.
for example, here is a list of titles of Emperor Charles V:
Emperor of the Romans;
King in Germany, of Castilia, Aragon, Leon, both Sicilies, Jerusalem, Hungary, Dalmatia, Croatia, Navarra, Grenada, Toledo, Valencia, Galicia, Majorca, Sevilla, Sardinia, Cordova, Corsica, Murcia, Jaen, the Algarves, Algeciras, Gibraltar, the Islands of Canary , of the Indies, Mainland of the Ocean sea;
Archduke of Austria;
Duke of Burgundy, Brabant, Lotharingia, Styria, Carinthia, Carniola, Limburg, Luxembourg, Gelderland, Athens, Neopatria, Württemberg;
Landgrave of Alsace;
Prince of Swabia, Asturia, Catalonia;
Count of Flanders, Habsburg, Tyrol, Gorizia, Barcelona, Artois, Burgundy Palatine, Hainaut, Holland, Seeland, Ferrette, Kyburg, Namur, Roussillon, Cerdagne, Zutphen,
Margrave of Burgau, Oristano, Gociano, the Holy Roman Empire;
Lord of Frisia, the Wendish March, Pordenone, Biscay, Molin, Salins, Tripoli, Mechelen;
http://www.eurulers.altervista.org/emperors.html
But those titles were not additional imperial titles so there is no need to give more examples.
In the eastern part of the Roman Empire, Greek was the highest status language after Latin, and spoken by many times as many people. Sometiemes the Latin titles of emperors were spoken, and transliterated in the Greek Alphabet.
And sometimes the imperial titles were translated int Greek more or less accurately. Autokrator became the usual translation of imperator, and Sebastos became the usual ranslation of Augustus.
And it was normal for Greek speekers to simply call the eperor the Basileus. The word Basileus orginally ment the king of a small Greek city state. In the Hellenistic age the mighty Ptolemaic and Seleucid monarchs used the title Basileus without a territorial qualification, and thus might have been claiming to be kings of the whole world.
When the Greeks called the emperor Basileus, or king, they might have ment not merely "a king" but "THE KING", the king of all the world.
As centuries passed the use of Latin declined in the eastern part of the Roman Empire and Greek became the language of government. By about AD 900 the imperial title was Basileus kai autokrator ton Rhomaion. That is usually translated as "Emperor and autocrat of the Romans". But since autokrator is a translation of imperator, it might be logical to consider Basileus kai autokrator to be a phrase meaning "emperor" and thus translate The title as "Emperor of the Romans". The most literal translation would be "King and emperor of the Romans". And another possible translation is "Emperor and emperor of the Romans".
In any case, a title including basileus and autokrator is another historical example of a title with redundent words meaning emperor and another precedent for padishah emperor.
The title of the Persian monarchs of the Achaemenid dynasty is usually given as "great king" or "king of kings", but the full title was more or less "The great king, the king of kings, the king of lands and peoples, the king of the world (or of the universe)".
So the full title of the Achaemenid rulers included two, three, or four phrases which might be considered to mean emperor.
And so the Achaemenid title counts as precedent for padishah emperor.
The Ottoman rulers used a long and elaborate full title. Shakespeare refers to it in the play King Henry VI Part I. Act IV, Scene VII:
The Turk, that two and fifty kingdoms hath,
Writes not so tedious a style as this.
http://www.shakespeare-online.com/plays/1kh6_4_7.html
According to Wikipedia, the full title became:
The full style of the Ottoman sultan once the empire's frontiers had stabilized became:4
"Sultan (given name) Han, Sovereign of The Sublime House of Osman, Sultan us-Selatin (Sultan of Sultans), Hakan (Khan of Khans), Commander of the faithful and Successor of the Prophet of the lord of the Universe, Custodian of the Holy Cities of Mecca, Medina and Kouds (Jerusalem), Kayser-i Rum (Caesar of Rome), Padishah (Emperor) of The Three Cities of Istanbul (Constantinople), Edirne (Adrianople) and Bursa, and of the Cities of Châm (Damascus) and Cairo (Egypt), of all Azerbaijan, of the Maghreb, of Barkah, of Kairouan, of Alep, of the Arab and Persian Iraq, of Basra, of El Hasa strip, of Raqqa, of Mosul, of Parthia, of Diyâr-ı Bekr, of Cilicia, of the provinces of Erzurum, of Sivas, of Adana, of Karaman, of Van, of Barbaria, of Habech (Abyssinia), of Tunisia, of Tripoli, of Châm (Syria), of Cyprus, of Rhodes, of Crete, of the province of Morea (Peloponnese), of Bahr-i Sefid (Mediterranean Sea), of Bahr-i Siyah (Black Sea), of Anatolia, of Rumelia (the European part of the Empire), of Bagdad, of Kurdistan, of Greece, of Turkestan, of Tartary, of Circassia, of the two regions of Kabarda, of Gorjestan (Georgia), of the steppe of Kipchaks, of the whole country of the Tatars, of Kefa (Theodosia) and of all the neighbouring regions, of Bosnia, of the City and Fort of Belgrade, of the province of Sirbistan (Serbia), with all the castles and cities, of all Arnaut, of all Eflak (Wallachia) and Bogdania (Moldavia), as well as all the dependencies and borders, and many others countries and cities."
https://en.wikipedia.org/wiki/List_of_Ottoman_titles_and_appellations#:~:text=The%20sovereigns%27%20main%20titles%20were%20Sultan%2C%20Padishah%20%28Emperor%29,to%20the%20various%20states%20it%20annexed%20or%20subdued.
And that seems to count as a precedent for padishah emperor. And note that padishah is actually part of the title.
The Mughal rules of India used titles like Padishah (lord or master of kings), Khagan (khan of khans), and Shahanshah Al-Sultanat Al-Hindiyyah Al-Mughaliyyah (king of kings of the Sultanate of India and the Mughals).
I have seen an example of a very long and elaborate Mughal title somewhere, but this is the best that I could find now.
https://en.wikipedia.org/wiki/Imperial_and_royal_titles_of_the_Mughal_emperors
So the Mughals also count as padishahs who use other more or less imperial titles.
And of course the Ottoman and Mughal courts were probably the inspirations for much of the court of the padishah emperor in Dune.
So I don't think that the title of padishah emperor is particularly redundent.
