Sachverhalt:
A. Am 24. Februar 2006, um 00.30 Uhr, überschritt X._ mit seinem Personenwagen auf der Autobahn A2 bei Tenniken die Höchstgeschwindigkeit von 120 km/h um 36 km/h (nach Abzug der Sicherheitsmarge).
Mit Strafbefehl vom 22. August 2006 büsste ihn die Statthalterin des Bezirks Sissach wegen einfacher Verkehrsregelverletzung nach <ref-law> mit Fr. 600.--. Der Strafbefehl ist rechtskräftig.
Mit Verfügung vom 3. Mai 2007 entzog die Kantonspolizei Basel-Stadt X._ den Führerausweis wegen schwerer Widerhandlung nach Art. 16c Abs. 1 lit. a i.V.m. Abs. 2 lit. a SVG für die Dauer von drei Monaten.
Den von X._ dagegen erhobenen Rekurs wies das Sicherheitsdepartement des Kantons Basel-Stadt am 11. Juni 2008 ab.
Den von X._ hiergegen eingereichten Rekurs wies das Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht) am 6. Mai 2009 ab.
B. X._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, das Urteil des Appellationsgerichts sei aufzuheben und von einer Administrativmassnahme abzusehen. Eventualiter sei das Urteil des Appellationsgerichts aufzuheben und der Beschwerdeführer in Anwendung von <ref-law> zu verwarnen.
C. Das Appellationsgericht und das Bundesamt für Strassen beantragen unter Hinweis auf den angefochtenen Entscheid je die Abweisung der Beschwerde.
Das Sicherheitsdepartement hat sich nicht vernehmen lassen.
D. Mit Verfügung vom 29. September 2009 hat der Präsident der I. öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung zuerkannt.

Erwägungen:
1. Gegen den angefochtenen Entscheid ist gemäss <ref-law> die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegeben.
Ein kantonales Rechtsmittel steht nicht zur Verfügung. Die Beschwerde ist nach Art. 86 Abs. 1 lit. d i.V.m. Abs. 2 BGG zulässig.
Der Beschwerdeführer ist gemäss <ref-law> zur Beschwerde befugt.
Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde einzutreten.
2. 2.1 Der Beschwerdeführer rügt, die Annahme einer schweren Widerhandlung nach <ref-law> verletze Bundesrecht.
2.2 Das Vorbringen ist offensichtlich unbegründet. Der Beschwerdeführer hat die Höchstgeschwindigkeit von 120 km/h auf der Autobahn unstreitig um 36 km/h überschritten. Nach der Rechtsprechung begeht ungeachtet der konkreten Umstände objektiv eine schwere Widerhandlung nach <ref-law>, wer die Höchstgeschwindigkeit auf der Autobahn um 35 km/h oder mehr überschreitet (<ref-ruling> E. 3 S. 237 ff.; <ref-ruling> E. 2a S. 477; je mit Hinweisen). Darauf zurückzukommen besteht kein Anlass (Urteil 1C_328/2008 vom 25. November 2008 E. 2.3 mit Hinweis). Die Annahme einer objektiv schweren Widerhandlung ist somit bundesrechtmässig. Der Beschwerdeführer dürfte die Höchstgeschwindigkeit vorsätzlich überschritten haben. Zumindest ist ihm insoweit grobe Fahrlässigkeit vorzuwerfen, weshalb eine schwere Widerhandlung nach <ref-law> auch in subjektiver Hinsicht gegeben ist (vgl. <ref-ruling> E. 1a S. 207; <ref-ruling> E. 2a S. 109).
Zwar trifft es zu, dass die Strafrichterin den Beschwerdeführer lediglich wegen einfacher Verkehrsregelverletzung nach <ref-law> gebüsst hat. Die einfache Verkehrsregelverletzung umfasst die leichte und mittelschwere Widerhandlung nach Art. 16a bzw. 16b SVG (<ref-ruling> E. 2.4 S. 143 f. mit Hinweisen). Nach der Rechtsprechung ist die Verwaltungsbehörde an die rechtliche Würdigung des Strafrichters dann gebunden, wenn diese sehr stark von der Würdigung von Tatsachen abhängt, die der Strafrichter besser kennt (<ref-ruling> E. 1 c/bb S. 106 f.; <ref-ruling> E. 3 c/bb S. 164). Dies trifft hier schon deshalb nicht zu, weil es nach der dargelegten Rechtsprechung auf die konkreten Umstände nicht ankommt.
Gemäss <ref-law> beträgt die Dauer des Führerausweisentzugs bei einer schweren Widerhandlung mindestens drei Monate. Auf diese Entzugsdauer haben die kantonalen Behörden erkannt.
Auf die überzeugenden Erwägungen der Vorinstanz zum Entzug (S. 4 ff. E. 4) kann im Übrigen verwiesen werden (vgl. <ref-law>).
3. 3.1 Der Beschwerdeführer macht geltend das Verfahren habe entgegen der Ansicht der Vorinstanz übermässig lange gedauert, was <ref-law> bzw. Art. 6 Ziff 1 EMRK verletze.
3.2 Nach dem mit der Revision des Strassenverkehrsgesetzes am 1. Januar 2005 in Kraft gesetzten <ref-law> darf die Mindestentzugsdauer nicht unterschritten werden. Dies gilt nach der Rechtsprechung - im Gegensatz zum früheren Recht - auch bei Verletzung des Anspruchs auf Beurteilung innert angemessener Frist nach <ref-law> und Art. 6 Ziff. 1 EMRK. Die Frage, ob bei einer schweren Verletzung dieses Anspruchs, der nicht in anderer Weise Rechnung getragen werden kann, ausnahmsweise gänzlich auf eine Massnahme verzichtet werden kann, liess das Bundesgericht offen (<ref-ruling> E. 2.2 f. S. 336 f.).
3.3 In <ref-ruling> ging es um eine am 7. Mai 2006 begangene Geschwindigkeitsüberschreitung. Der Strafbefehl erging am 29. August 2006. Am 31. Januar 2007 entzog die Verwaltungsbehörde den Führerausweis unter Annahme einer schweren Widerhandlung für die Dauer von drei Monaten. Den dagegen erhobenen Rekurs wies der Regierungsrat am 7. Mai 2008 ab. Das kantonale Verwaltungsgericht entschied am 11. Februar 2009. Das gesamte Verfahren von der Widerhandlung bis zum bundesgerichtlichen Urteil dauerte knapp 3 Jahre und 4 Monate.
Das Bundesgericht bejahte mit dem Verwaltungsgericht eine Verletzung des Anspruchs auf Beurteilung innert angemessener Frist, verneinte dagegen eine schwere Verletzung dieses Anspruchs. Es erachtete den gänzlichen Verzicht auf eine Massnahme daher als nicht statthaft; ebenso wenig die Unterschreitung der Mindestentzugsdauer von drei Monaten. Es hob den Entscheid des Verwaltungsgericht, das wegen der Verletzung des Beschleunigungsgebots einen Führerausweisentzug von zwei Monaten festgesetzt hatte, insoweit auf, ordnete einen Führerausweisentzug von drei Monaten an und stellte die Verletzung des Anspruchs auf Beurteilung innert angemessener Frist im Dispositiv fest.
3.4 Im vorliegenden Fall beging der Beschwerdeführer die Geschwindigkeitsüberschreitung am 24. Februar 2006. Am 22. August 2006 erging der Strafbefehl. Die Kantonspolizei verfügte den Führerausweisentzug am 3. Mai 2007. Seit dem Strafbefehl waren damit gut acht Monate verstrichen. Das Sicherheitsdepartement entschied darauf am 11. Juni 2008, rund elf Monate nach Abschluss des Schriftenwechsels bei ihm Mitte Juli 2007. Die Vorinstanz fällte ihr Urteil am 6. Mai 2009, ca. 6 1⁄2 Monate nach Abschluss des Schriftenwechsels bei ihm am 20. Oktober 2008. Seit der Widerhandlung des Beschwerdeführers sind heute mehr als vier Jahre verstrichen.
Der Fall ist weder in tatsächlicher noch rechtlicher Hinsicht komplex. In Anbetracht dessen müssen insbesondere die elf Monate, die das Sicherheitsdepartement bis zu seinem Entscheid brauchte, als übermässig lange beurteilt werden. Auch die gesamte Verfahrensdauer von nunmehr über vier Jahren ist zu lang. Wie der Beschwerdeführer zutreffend vorbringt, kann es ihm entgegen der Andeutung im angefochtenen Entscheid (S. 6 E. 5) nicht zum Vorwurf gereichen, dass er alle Rechtsmittel ausgeschöpft hat. Dazu war er berechtigt. Eine Verletzung des Anspruchs auf Beurteilung innert angemessener Frist nach <ref-law> und Art. 6 Ziff. 1 EMRK ist unter den gegebenen Umständen zu bejahen. Die Verletzung wiegt allerdings nicht so schwer, dass ein Verzicht auf den Führerausweisentzug in Frage käme. Es ist nicht ersichtlich, dass der Entzug wegen des Zeitablaufs keine erzieherische Wirkung mehr haben könnte. Der vorliegende Fall ist vergleichbar mit jenem, den das Bundesgericht in <ref-ruling> zu beurteilen hatte. Die Mindestentzugsdauer darf folglich nicht unterschritten werden. Die Verletzung des Anspruchs auf Beurteilung innert angemessener Frist ist jedoch (im Dispositiv) ausdrücklich festzustellen, was für den Beschwerdeführer eine Form der Wiedergutmachung darstellt (<ref-ruling> E. 3 S. 337; <ref-ruling> E. 5.3 S. 333; <ref-ruling> E. 1.3 S. 417; je mit Hinweisen).
4. Nach dem Gesagten ist die Beschwerde teilweise gutzuheissen.
Soweit der Beschwerdeführer unterliegt, trägt er eine reduzierte Gerichtsgebühr (<ref-law>).
Soweit er obsiegt, hat ihm der Kanton eine Entschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG).
Bei der Festsetzung der Höhe der Gerichtsgebühr und der Entschädigung wird zugunsten des Beschwerdeführers berücksichtigt, dass die Vorinstanz den Rekurs teilweise hätte gutheissen müssen mit den entsprechenden Kosten- und Entschädigungsfolgen. Wird mit Blick darauf im bundesgerichtlichen Verfahren eine tiefere Gerichtsgebühr erhoben bzw. eine höhere Entschädigung zugesprochen, als das sonst der Fall wäre, kann auf die Rückweisung der Akten an die Vorinstanz zur neuen Festsetzung der Kosten- und Entschädigungsfolgen des kantonalen Verfahrens verzichtet werden.

Demnach erkennt das Bundesgericht:
1. In teilweiser Gutheissung der Beschwerde wird festgestellt, dass der Anspruch des Beschwerdeführers auf Beurteilung innert angemessener Frist verletzt worden ist. Im Übrigen wird die Beschwerde abgewiesen.
2. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
3. Der Kanton Basel-Stadt hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 1'500.-- zu bezahlen.
4. Dieses Urteil wird dem Beschwerdeführer, dem Sicherheitsdepartement und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht sowie dem Bundesamt für Strassen schriftlich mitgeteilt.
Lausanne, 30. März 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Härri