IF they constituted 1 million, it would have been very difficult to defeat them.
And you claim that it wasn't?
It took the Franks (later the Germans that emerged from Eastern Francia) about 500 - 600 years to completely conquer all areas to the east of the Oder-Neisse line (or the present-day border of Germany). By contrast conquering the Saxons (who were also Pagans until they were forcibly converted by the Franks) took only several decades. You claimed that first evidence of Slavs in East Germany and Austria is from the 700s, but that's not true (see below - first archaeological evidence is from ca. 550-600, first written sources from the 600s). And when the Obodrites and the Veleti were first mentioned, they were already strong established tribal unions, so they must have existed for some time before that.
Below is the early timeline of the history of Slavs in Germany - until Charlemagne's death. From Charlemagne's death it took about 400 more years to conquer them (but for example the Veleti and the Obodrites were conquered by Germans already in 963, but in 983 they started the Great Slav Rising and became independent again - following that Great Slav Rising they were independent for the next 200 years, until 1150-1200, some of them even longer up to 1250, when Germans finally captured all areas to the west of the Oder-Neisse line, the present-day border of Germany):
http://en.wikipedia.org/wiki/Great_Slav_Rising
Early timeline of Slavs in Germany (until Charlemagne's death in 814; the next period from 814 to 1250 was even more interesting). Slavic colonization of what is now East Germany (and what used to be part of West Slavdom before the Northern Crusades) started in the 6th century.
Here is the timeline of the earliest phase of history of Slavs in Germany, from the beginning of historical record until the death of Charlemagne:
⦁ 512 - the Heruli migrate from middle Danube to North Germany and encounter territories already inhabited by Slavs on their way there (source: Procopius)
⦁ 6th century - Slavic settlement at Prague, Bohemia, numbers over 600 houses:
http://www.archaeobotany.org/download/posters/novak_roztoky_abstract_whv2010.pdf
⦁ ca. 550 - Slavs start migrating into what is now East Germany
⦁ 595 - Slavs (probably ancestors of Slovenes or / and Croats) fight against Frankish-dependent Bavarian duke Tassilo in modern Austria and Bohemia
⦁ 596 - Slavs, probably allied with the Avars, defeat the Bavarians under Tassilo, killing 2,000 of them
⦁ 610 - battle of Aguntum (4 km to the east of present-day Lienz), Bavarians finally stop Slavic westward expansion in this region (source: Paul the Deacon)
⦁ 620s - a major war between Slavs and Avars (who had previously been allies)
⦁ 624 - a smuggler of weapons from the Frankish Empire, Samo (born near Sens at the Yonne river in central France), who had previously been illegally smuggling across the border and selling weapons to Slavs, enters Slavic lands, joins Slavs in their fight against the Avars, and due to his merits in battle, united Slavic tribes elect him their king (source: Fredegar's chronicle). Samo was probably a Gallo-Roman.
⦁ 630 - Walluk, duke of Carantanians (northern Slovenes), joins Samo's Federation.
⦁ 631 - Slavic Federation defeats the Frankish Empire in the battle of Wogastisburg
⦁ 631 - after the victory at Wogastisburg Slavic armies invade and plunder Thuringia
⦁ 632 - Dervan, duke of Surbi (Sorbs) joins the Slavic Federation under king Samo
⦁ 636 - Dervan is killed in one of battles against Randulf, governor of Thuringia
⦁ 661 - the federation disintegrates into many realms again after Samo's death. According to Fredegar's chronicle Samo had 12 Slavic wifes, 22 sons and 15 daughters.
⦁ 772 - Charlemagne invades Southern Saxons (who are Pagans)
⦁ 777 - the conquest of Southern Saxons by the Franks is completed
⦁ 780 - first Frankish contact with the Slavic Obodrites at the Middle Elbe
⦁ 782 - Slavic Sorbs raid and plunder Thuringia and Frankish-controlled Saxony
⦁ 782 - Saxon uprising against Franks, led by Saxon duke Widukind. Obodrites side with Franks
⦁ 785 - uprising squashed, Widukind surrenders and agrees to convert to Christianity in Attigny
⦁ 789 - Wieczan (Witzan) becomes the supreme duke (rex / princeps) of Obodrites
⦁ 789 - Obodrites mentioned as "old good allies" of Charlemagne (against Saxons)
⦁ 789 - Wieczan asks Charlemagne for assistance against his troublesome eastern neighbours, the Holy Union of the Veleti, under supreme duke Drogowit.
⦁ 789 - Charlemagne, allied with Frisians, Sorbs and Obodrites (under duke Wieczan), invades Veleti. Frankish army crosses the Elbe near modern Wolmirstadt. Allied forces besiege Brenna, the main stronghold of Veleti duke Drogowit. Seeing that resistance is pointless, Drogowit negotiates peace. Veleti pay a single tribute to Charlemagne. Charlemagne satisfied with tribute returns back to Francia.
⦁ 795 - Obodrite duke Wieczan (dux Witzan), ally of Franks against Nordalbingians (northernmost Saxon tribe, who remain independent from Frankish rule).
⦁ 795 - at the Elbe near Bardowick Nordalbingians ambush Obodrites, killing Wieczan
⦁ ca. 796 - Drozko elected new rex / princeps of the Obodrites. Drozko has a son named Czedrog (Chedrog). Drozko continues pro-Frankish policies of Wieczan and Charlemagne is his ally. Danes, Northern Saxons and Veleti are his enemies.
⦁ 795-798 - in revenge for Wieczan's death, Charlemagne raids Nordalbingians and carries out first forcible population transfers and deportations of Saxons.
⦁ 798 - battle of Swentana (Bornhöved) between Obodrites under Drozko and Nordalbingians (at the same time Charlemagne's army is near Minden, raiding Ostphalia). Obodrites win. About 3 - 4 thousand Saxons perish.
⦁ 799 - son of Charlemagne mediates in conflict between Obodrites and Veleti
⦁ 804 - conquest of Nordalbingians by Franks (with Veleti help) is completed, forcible deportation of over 10,000 Nordalbingian men, with families, to Gaul.
⦁ 804 - in Hollenstedt at the Elbe Drozko is crowned King by Charlemagne, he is also awarded Nordalbingia, which becomes part of the Slavic Obodrite realm (sources: Ann. Regni Francorum a 804, Chron. Moiss a 804). Archaeological evidence of Slavic settlements and Slavic pottery in Nordalbingia discovered in Hamburg and in Domplatz, dated to 8th-9th centuries (R. Schindler connects these with Drozko's reign).
⦁ ca. 805 - Charlemagne fortifies Frankish-Slavic border (limes sorabicus and limes saxonicus) and establishes permanent military posts along it. He introduces capitulare duplex in 805 - a kind of embargo for export of weaponry to Slavic lands (including even his allied Obodrites). Several places are chosen for trade with Slavs.
⦁ 805 - Franks invade the Sorbian-Lusatian tribe of the Glomaci
⦁ 805 - duke Lecho of the Bohemians (Czechs) dies in battle against Charlemagne
⦁ 806 - Sorbs (Siurbs) agree to pay tribute to Charlemgne after their duke - Miliduch (Milidouch / Milito) - is killed in a battle against Franks near modern Halle.
⦁ 808 - Drozko, king of the Obodrites. Godelaib, one of their minor dukes.
⦁ 808 - the Danes under duke Godfred (his realm is in Jutland), allied with the Veleti, invade the Obodrite realm (Jutland had previously become a refuge for Saxon refugees during Frankish-Obodrite invasions of Nordalbingia). Danes and Veleti manage to capture several Obodrite strongholds in the process.
⦁ 808 - at least two out of member-tribes of the Obodrite realm, Smolincy and Linianie, betray and unite with Danish-Veleti army. King Drozko is forced to abandon his realm and escapes to Francia. Godelaib is captured and executed. Godfred annexes Nordalbingia, two other Obodrite provinces - Obodrsko and Wagria - pay tribute.
⦁ 808-809 - Veleti wage offensive war against Obodrites and then against Franks
⦁ 808 - Charlemagne sends his son to crush the Veleti and Obodrite traitors, but he is defeated and has to retreat. Godfred proposes peace to Charlemagne, negotiations take place in Bandenflut at the Stör River, but they fail and war continues on.
⦁ 809 - Drozko returns from exile to his country. He signs truce with Danes in exchange for giving them one of his sons (maybe Chedrog) as a hostage. He allies with Saxons against Veleti and these Obotrite trines which seceded from his realm. Allied Obodrite loyalists and Saxons besiege a stronghold of Smolincy at Connoburg. The stronghold is captured and destroyed, power over rebellious tribes is restored.
⦁ 809 - Godfred violates the truce and invades Obodrites, he demolishes Slavic coastal town at Rerik (near modern Wismar), and deports local merchants to Haithabu (Hedeby), Denmark. Drozko is killed by Danish assassins at Rerik.
⦁ 809 - after the death of Drozko Charlemagne deprives the Obodrites of Nordalbingia (land of Northern Saxons) and incorporates it to his Empire. The land is depopulated due to war, disease and deportations, so he brings in new settlers from entire Empire. Charlemagne establishes three new castles to strengthen the defence of his borders: first is at Eselfeld at the Stör River, second is at Hamburg, third is at Hochbucki near Lenzen at the Elbe.
⦁ 810 - Veleti attack the Frankish Empire and destroy their new castle at Hochbucki
⦁ 812 - Franks and Obodrites (under their new grand duke, Slavomir) in retaliation invade Veleti territories and manage to force them to pay a tribute.
⦁ 813 - coronation of Louis I by Charlemagne in Aachen.
⦁ 814 - death of Charlemagne, Louis I takes power in the Empire. Those of Slavic tribes which had been paying tribute to Charlemagne, stop paying it.