Sachverhalt:
A. Die Staatsanwaltschaft Zürich ermittelt gegen X._ wegen des Verdachts des mehrfachen Betrugs, des mehrfachen betrügerischen Missbrauchs einer Datenverarbeitungsanlage, der mehrfachen Veruntreuung, der mehrfachen Urkundenfälschung sowie der Begünstigung, der Zechprellerei, des Erwerbs und Konsums von Marihuana sowie Verstössen gegen das Strassenverkehrsgesetz. X._ wurde am 5. Juni 2007 verhaftet und am 7. Juni 2007 in Untersuchungshaft versetzt. Am 18. Februar 2009 wurde er aus der Haft entlassen.
B. Am 13. Februar 2009 erhob X._ Rekurs bei der Oberstaatsanwaltschaft des Kantons Zürich wegen Verfahrensverschleppung. Am 23. April 2009 wies die Oberstaatsanwaltschaft den Rekurs ab.
C. Dagegen hat X._ am 28. Mai 2009 Beschwerde ans Bundesgericht erhoben. Er beantragt, es sei festzustellen, dass eine Verfahrensverzögerung vorliege; die Staatsanwaltschaft Zürich-Sihl sei anzuweisen, das Untersuchungsverfahren gegen ihn ab sofort beförderlich zu führen. Eventualiter seien die Kosten- und Entschädigungsfolgen im vorinstanzlichen Verfahren unter Berücksichtigung des abgewiesenen Nichteintretensantrags der Staatsanwaltschaft angemessen zu korrigieren. Zudem ersucht der Beschwerdeführer um unentgeltliche Verbeiständung.
D. Die Oberstaatsanwaltschaft beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen. Die Staatsanwaltschaft Zürich-Sihl schliesst auf Abweisung der Beschwerde.

Erwägungen:
1. Angefochten ist ein Entscheid der Oberstaatsanwaltschaft Zürich, der einen Rekurs wegen Verschleppung eines Strafverfahrens abweist. Die Beschwerde betrifft somit eine strafrechtliche Angelegenheit und ist als Beschwerde in Strafsachen entgegen zu nehmen (<ref-law>). Nach § 409 der Zürcher Strafprozessordnung (StPO/ZH) ist der Rekursentscheid der Oberstaatsanwaltschaft endgültig und damit kantonal letztinstanzlich (Art. 80 Abs. 1 i.V.m. <ref-law>).
1.1 Der angefochtene Entscheid ist ein Zwischenentscheid i.S.v. <ref-law>, gegen den die Beschwerde in Strafsachen (abgesehen vom hier nicht gegebenen Ausnahmefall nach <ref-law>) nur zulässig ist, wenn er einen nicht wieder gutzumachenden Nachteil bewirken kann (lit. a). Dies wird grundsätzlich bejaht, wenn - wie hier - eine ungerechtfertigte Verfahrensverzögerung bzw. Rechtsverweigerung geltend gemacht wird (<ref-ruling> E. 1.3 S. 129; <ref-ruling> E. 2 S. 44 ff.; je mit Hinweisen).
1.2 Der Beschwerdeführer rügt die Verletzung des in Art. 29 Abs. 1 und Art. 6 Ziff. 1 EMRK verankerten Beschleunigungsgebots. Die Verletzung von Grundrechten wird vom Bundesgericht nicht von Amtes wegen geprüft, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Für derartige Rügen gelten die gleichen Begründungsanforderungen, wie sie gestützt auf Art. 90 Abs. 1 lit. b OG für die staatsrechtliche Beschwerde gegolten haben (<ref-ruling> E. 1.4.2 S. 254 mit Hinweisen). Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Erlass oder Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen; auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (<ref-ruling> E. 1.3 S. 261 f. mit Hinweisen). Inwieweit diese Anforderungen erfüllt sind, ist im Folgenden für jede Rüge gesondert zu prüfen.
2. Die Oberstaatsanwaltschaft überprüfte die Verfahrensführung ab Januar 2008 bis zur Rekurserhebung am 13. Februar 2009, weil sie davon ausging, dass nur für diese Periode eine Verfahrensverschleppung gerügt worden sei. Der Beschwerdeführer bestreitet dies und macht geltend, er habe die ganze Untersuchungsperiode bis zum Zeitpunkt der Rekurserhebung kritisiert. Er belegt dies aber nicht anhand seiner Rekursschrift. Im Übrigen geht er in seiner Beschwerdeschrift selbst davon aus, dass die polizeilichen Ermittlungen erst Ende 2007 abgeschlossen worden seien. Auch die in der Beschwerdeschrift zitierten Reklamationen bei der Staatsanwaltschaft Zürich-Sihl datieren vom 7. Oktober 2008 bis 13. Januar 2009. Diesbezüglich fehlt es somit an einer genügenden Beschwerdebegründung.
Daher ist auch im Folgenden nur zu prüfen, ob in der Zeit von Januar 2008 bis zur Rekurserhebung (am 13. Februar 2009) das Beschleunigungsgebot verletzt wurde.
Damit kann die vom Beschwerdeführer bestrittene Zahl der polizeilichen Einvernahmen offen bleiben, da diese im Wesentlichen in das Jahr 2007 fallen.
3. Der Beschwerdeführer stützt den Vorwurf der Verfahrensverschleppung auf eine von ihm erstellte tabellarische Übersicht über die bisher vorgenommenen staatsanwaltschaftlichen Einvernahmen. Daraus ergebe sich seit seiner Verhaftung bis zur Rekurserhebung eine Gesamtlänge von 45 Stunden und 45 Minuten, was auf den Monat umgerechnet gerade einmal 2 1⁄4 Stunden ergebe. Hätte der Staatsanwalt die Einvernahmen kompakt geführt, hätte er damit theoretisch in einer einzigen Woche fertig werden können. Hätte er diese z.B. Anfang Januar 2008 durchgeführt, hätte das Untersuchungsverfahren in der ersten Januarhälfte 2008 abgeschlossen werden können. Zudem zeige die Tabelle, dass der Staatsanwalt jeweils nach bewilligter Haftverlängerung nichts mehr vorgenommen, sondern Einvernahmen jeweils ca. 30 bis 35 Tage vor Ablauf der Haftbewilligung durchgeführt habe, um Betriebsamkeit vor dem Haftrichter vorzutäuschen.
3.1 Die Oberstaatsanwaltschaft ging dagegen davon aus, dass sich aufgrund der Einvernahmedauer allein nicht beurteilen lasse, ob das Verfahren beförderlich geführt worden sei oder nicht. Geradezu utopisch mute die Vorstellung des Beschwerdeführers an, wonach sämtliche Einvernahmen in einer Woche hätten durchgeführt werden können. Dies sei allein schon aufgrund der terminlichen Abkömmlichkeiten der Beteiligten (Zeugen, Auskunftspersonen, Verteidiger) nicht möglich. Zudem müsse sich die Staatsanwaltschaft vor der Durchführung weiterer Einvernahmen jeweils mit den früheren Aussagen auseinandersetzen und diese anhand weiterer Dokumente überprüfen (wie z.B. der anlässlich der Zeugenbefragung vom 27. November 2008 eingereichten Unterlagen). Würden alle Einvernahmen an einem Stück durchgeführt, wäre dies der Wahrheitsfindung nicht zuträglich und würde auch die Verteidigungsrechte massiv tangieren, da der Angeschuldigte selbst keine Zeit zur Vorbereitung hätte.
Entscheidend für die Beurteilung der Angemessenheit der Verfahrensdauer sei vielmehr eine Gesamtbetrachtung des konkreten Einzelfalls, unter Berücksichtigung insbesondere der Schwere des Tatvorwurfs, der Komplexität des Sachverhaltes und des Verhaltens des Angeschuldigten. Zwar könnten die dem Beschwerdeführer vorgeworfenen Delikte als solche nicht als äussert komplex bezeichnet werden; aufgrund der Vielzahl der Delikte und der damit verbundenen Befragungen und Einvernahmen verschiedener Personen müsse jedoch von einem grundsätzlich komplexen Verfahren gesprochen werden, welches derzeit in 12 Bundesordnern dokumentiert sei. Die vom Beschwerdeführer eingereichte Tabelle sei unvollständig und enthalte beispielsweise nicht die Einvernahmen vom 16. Mai 2008 und vom 4. November 2008. Von Januar 2008 bis zum 18. Februar 2009 habe die Staatsanwaltschaft ca. 36 Einvernahmen durchgeführt. Allein daraus sei ersichtlich, dass die Staatsanwaltschaft 2008 nicht untätig geblieben sei, sondern sich mit dem Strafverfahren regelmässig befasst habe.
3.2 Die Ausführungen der Oberstaatsanwaltschaft zur Notwendigkeit einer Gesamtbetrachtung und den dabei massgeblichen Kriterien entsprechen der bundesgerichtlichen Rechtsprechung (vgl. <ref-ruling> E. 2c S. 142; <ref-ruling> E. 3.3.3 S. 56). Da sich die Strafverfolgungsbehörde nicht ständig mit einem einzigen Fall befassen kann, sind Zeiten, in denen das Verfahren stillsteht, unumgänglich und führen per se nicht zu einer Verletzung des Beschleunigungsgebots. Solange keine einzelne solche Zeitspanne stossend wirkt, greift die Gesamtbetrachtung. Als stossend wurde beispielsweise eine Untätigkeit von 13 bis 14 Monaten im Untersuchungsverfahren angenommen (vgl. BGE <ref-ruling> E. 3.3.3 S. 56 f.).
3.3 Der Beschwerdeführer setzt sich in seiner Beschwerde nicht näher mit den Ausführungen der Oberstaatsanwaltschaft zu Komplexität und Umfang des Strafverfahrens auseinander und legt nicht dar, inwiefern die Gesamtdauer des bisherigen Verfahrens dazu in einem Missverhältnis steht. Aus der von ihm erstellten Tabelle ergibt sich sodann, dass zwischen zwei Einvernahmen z.T. mehrere Wochen vergangen sind; die Tabelle weist aber keine wirklich stossenden Zeiten der Untätigkeit auf. Das längste Intervall zwischen zwei Einvernahmen (vom 26. Februar 2008 bis zum 7. Mai 2008) beträgt zweieinhalb Monate; in diesem Zeitraum wurden jedoch mehrere polizeiliche Nachtragsberichte zu den Akten gegeben (vgl. angefochtenen Entscheid E. 6.4 S. 8) und das Untersuchungsverfahren somit vorangetrieben. Der Beschwerdeführer legt auch nicht substantiiert dar, welche Einvernahmen und Befragungen wesentlich früher hätten durchgeführt werden können und inwiefern die Gesamtdauer des Verfahrens damit erheblich verkürzt hätte werden können. Offensichtlich unzutreffend ist die Vorstellung, in einem umfangreichen Verfahren wie dem Vorliegenden könnten alle Einvernahmen "kompakt" innerhalb einer Woche durchgeführt werden; hierfür kann auf die zutreffenden Ausführungen des Rekursentscheids verwiesen werden.
3.4 Soweit der Beschwerdeführer geltend macht, der Staatsanwalt habe ein Fax-Schreiben des Verteidigers in Verletzung von § 194 Abs. 2 GVG/ZH nicht an den Haftrichter weitergeleitet (vgl. dazu das bundesgerichtliche Urteil 1B_172/2008 vom 17. Juli 2008), handelte es sich um ein Versehen, welches das Untersuchungsverfahren - wenn überhaupt - nur geringfügig verlängert hat.
3.5 Schliesslich verweist der Beschwerdeführer auf Entscheide des Haftrichters, in denen zwar keine Verletzung des Beschleunigungsgebots festgestellt worden sei, die Staatsanwaltschaft Zürich-Sihl aber angehalten worden sei, in zukünftigen Haftanträgen detailliert Auskunft darüber zu geben, welche Untersuchungshandlungen noch durchzuführen seien, insbesondere welche Zeugen und Auskunftspersonen zu welchem Zeitpunkt einvernommen werden sollen, wann die Schlusseinvernahme stattfinden solle und wann mit der Anklageerhebung zu rechnen sei. Aus diesen Ausführungen lässt sich jedoch allenfalls entnehmen, dass die Haftanträge der Staatsanwaltschaft unzureichend begründet waren, namentlich im Hinblick auf die damals angenommene Kollusionsgefahr. Dagegen ergibt sich daraus allein kein Hinweis auf eine Verfahrensverschleppung. Gleiches gilt für den Hinweis des Haftrichters auf die Unüblichkeit von Teil-Schlusseinvernahmen. Die Gesamtdauer der Haft ist nicht Thema des vorliegenden Verfahrens und deshalb nicht zu prüfen.
4. Überdies rügt der Beschwerdeführer, ihm seien die gesamten Rekurskosten von Fr. 900.-- auferlegt worden, obwohl auch die Staatsanwaltschaft mit ihrem Hauptantrag auf Nichteintreten nicht durchgedrungen sei.
Die Oberstaatsanwaltschaft hat hierzu in ihrer Vernehmlassung ausgeführt, das Rekursverfahren sei kein Zivilverfahren, in dem die Begehren der jeweiligen Parteien einander gegenübergestellt werden; vielmehr richte sich die Beurteilung der Kostenfolge nur nach den Anträgen des Rekurrenten und ob er mit diesen durchdringe oder unterliege. Praxisgemäss sei es daher für die Kostenfolge unerheblich, ob die Staatsanwaltschaft einen Nichteintretensantrag gestellt habe oder nicht.
Diese Ausführungen lassen keine Willkür erkennen. Im Übrigen wäre der Kostenentscheid selbst dann nicht willkürlich, wenn auf die Anträge beider Parteien abgestellt würde: Die Staatsanwaltschaft drang zumindest mit ihrem Eventualantrag auf Rekursabweisung durch, während der Beschwerdeführer mit seinen Anträgen vollständig unterlag.
5. Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist.
Aufgrund der ungenügenden Begründung der Beschwerdeschrift, die sich kaum mit dem angefochtenen Rekursentscheid auseinandersetzt, war die Beschwerde von Anfang an aussichtslos. Das Gesuch um unentgeltliche Verbeiständung ist daher abzuweisen (Art. 64 Abs. 1 und 2 BGG); dagegen ist den vermögensrechtlichen Verhältnissen des Beschwerdeführers bei der Festsetzung der Gerichtsgebühr Rechnung zu tragen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 300.-- werden dem Beschwerdeführer auferlegt.
4. Es werden keine Parteientschädigungen zugesprochen.
5. Dieses Urteil wird dem Beschwerdeführer, der Staatsanwaltschaft Zürich-Sihl und der Oberstaatsanwaltschaft des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 14. Juli 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber