Sachverhalt: A. Die X._ GmbH (Klägerin, Beschwerdegegnerin) mit Sitz in I._ (Deutschland) ist als Technologie- und Dienstleistungsunternehmen insbesondere im Bereich der Kraftfahrzeugtechnik tätig. Sie ist Inhaberin des europäischen Patents EP xxx. Die Schweiz ist ein Benennungsland dieses Patents. Die Schweizerische Eidgenossenschaft (Beklagte, Beschwerdeführerin) erhebt seit dem 1. Januar 2001 über die Eidgenössische Zollverwaltung die in Art. 85 BV vorgesehene leistungsabhängige Schwerverkehrsabgabe (LSVA) nach den Bestimmungen des Bundesgesetzes vom 19. Dezember 1997 über eine leistungsabhängige Schwerverkehrsabgabe (Schwerverkehrsabgabegesetz, SVAG; SR 641.81). Die Abgabe wird auf den im In- und Ausland immatrikulierten schweren Motorfahrzeugen und Anhängern für den Güter- oder den Personentransport erhoben (Art. 3 SVAG), wobei sich die Höhe der Abgabe nach dem höchstzulässigen Gesamtgewicht des Fahrzeugs und den gefahrenen Kilometern bemisst (Art. 6 Abs. 1 SVAG) Bei den inländischen Fahrzeugen wird die Abgabe mit einem von der Zollverwaltung zugelassenen elektronischen Messgerät ermittelt. Das Erfassungsgerät (sog. On-Board-Unit) ermittelt und registriert die massgebende Fahrleistung; es wird von der Oberzolldirektion kostenlos abgegeben und ist vom Motorfahrzeughalter auf eigene Kosten einzubauen. Dabei wird das Erfassungsgerät mit dem Fahrtenschreiber des Fahrzeugs gekoppelt. Da insbesondere die inländischen Fahrzeuge sehr lange in der Schweiz unterwegs sein können, ohne jemals an die Landesgrenze zu kommen, stehen an gewissen Stellen des schweizerischen Autobahnnetzes ortsfeste Kontrollanlagen (sog. Baken), die mit den On-Board-Units kommunizieren. Für die in der Schweiz immatrikulierten Fahrzeuge ist die Installation einer On-Board-Unit obligatorisch; bei ausländischen Lastwagen kann das Gerät auf freiwilliger Basis eingesetzt werden. Die Fahrzeuge werden von den ortsfesten Kontrollanlagen erfasst, wobei die Daten der On-Board-Unit über eine Funkverbindung ausgelesen und mit den von der Anlage elektronisch gemessenen Daten automatisch verglichen werden. Die beklagte Eidgenossenschaft führte im Jahre 1994 für die Entwicklung eines Systems zur Erfassung der Fahrleistung ein öffentlichrechtliches Submissionsverfahren durch. Auch die Klägerin nahm an diesem Verfahren teil und präsentierte ein entsprechendes Systemkonzept. Mit Verfügung vom 21. April 1999 ging der Zuschlag an das Konsortium Y._. Für die strassenseitige Infrastruktur nahm die Beklagte eine weitere öffentliche Ausschreibung vor, wobei die Klägerin bei dieser als Unterlieferantin einer der Bewerberinnen beteiligt war. Mit Verfügung vom 31. März 1999 ging der Zuschlag an die Z._ AG. B. B.a. Die X._ GmbH klagte am 12. Mai 2011 beim Handelsgericht des Kantons Zürich gegen die Schweizerische Eidgenossenschaft mit den folgenden (im Rahmen des Verfahrens abgeänderten) Rechtsbegehren: "1. Es sei der Beklagten zu verbieten, ein System zum Erfassen der von einem Motorfahrzeug mit einem zulässigen Gesamtgewicht von mehr als 3.5 Tonnen in der Schweiz zurückgelegten Fahrstrecke zur Gebührenerhebung zu unterhalten und zu betreiben, das die folgenden Merkmale aufweist: - Im Motorfahrzeug mit einem zulässigen Gesamtgewicht von mehr als 3.5 Tonnen ist ein Fahrzeuggerät installiert, das fortlaufend und unabhängig vom jeweiligen Ort die gefahrene Strecke messen kann, - zwischen Fahrzeuggerät und Fahrtenschreiber besteht eine technische Verbindung, über die das Fahrzeuggerät Signale erhält, die zur Bestimmung der Wegstrecke dienen, - an den Landesgrenzen und im Landesinnern sind Feststationen installiert, die die vom Fahrzeuggerät ausgesendeten Daten empfangen können, - das Fahrzeuggerät kann beim Passieren einer Feststation den aktuellen Kilometerstand sowie eine eindeutige Identifikationsnummer an die Feststation übermitteln, - d ie Feststationen leiten die empfangenen Daten zusammen mit Informationen über Einfahrt in oder Ausfahrt aus der Schweiz an eine Zentrale zur Erhebung der Gebühr weiter. 2. Das Verbot gemäss Rechtsbegehren 1. sei unter Androhung von angemessenen Vollstreckungsmassnahmen auszusprechen. 3. a) Die Beklagte sei zu verpflichten, der Klägerin den Betrag von CHF 62'466'022.85 samt Zinsen zum Satz von 5 Prozentpunkten seit dem 12. Mai 2011 zu bezahlen. 3.b) Eventualiter sei der Betrag, den die Beklagte an die Klägerin zu bezahlen hat, gemäss Art. 42 Abs. 2 OR nach richterlichem Ermessen zu schätzen. 3.c) Die Klage erfolgt unter dem Vorbehalt der Nachklage. Alles unter Kosten- und Entschädigungsfolgen (inkl. MWST soweit anfallend) zulasten der Beklagten." Mit Beschluss vom 17. Januar 2012 überwies das Handelsgericht des Kanton Zürich das Verfahren an das Bundespatentgericht. Die Klägerin wirft der Beklagen eine Verletzung von EP xxx vor und macht geltend, die schädigende Handlung bestehe im Betrieb des LSVA-Erfassungssystems. Verletzende Handlungen erfolgten unter anderem bei der Erfassung des Grenzübertritts von Fahrzeugen mit Fahrzeuggeräten durch fix installierte Bakenanlagen. An der Schweizer Landesgrenze seien mindestens 80 Zollämter mit Bakenanlagen ausgerüstet; zudem seien im Landesinnern zu Kontrollzwecken an Autobahnen 23 Bakenanlagen fix installiert. Die patentierte Erfindung beschreibe ein Mauterfassungssystem, wie es die Schweiz für die LSVA kenne. Die Beschwerdeführerin bestritt die Zuständigkeit des Bundespatentgerichts und beantragte, es sei auf die Klage nicht einzutreten. B.b. Mit Beschluss vom 7. Juni 2012 erklärte sich das Bundespatentgericht für zuständig und trat auf die Klage ein. Das Gericht hielt fest, dass das Patentgesetz unter Hinweis auf das Enteignungsgesetz für die Enteignung ein öffentlichrechtliches Verfahren vorsehe (Art. 32 PatG), wogegen ein Anspruch auf eine Zwangslizenz (Art. 40 PatG) auf dem Zivilrechtsweg geltend zu machen sei. Sowohl die Enteignung als auch die Zwangslizenz setzten das Bestehen eines öffentlichen Interesses voraus, woraus zu schliessen sei, dass die Voraussetzung eines öffentlichen Interesses im Patentrecht nicht einzig entscheidendes Kriterium für die Abgrenzung zwischen einer streitigen Zivilsache und einer öffentlichrechtlichen Streitsache sein könne. Das Bundespatentgericht führte zudem aus, in Bezug auf die Frage, ob die Beklagte möglicherweise mit dem von ihr angewendeten LSVA-Erfassungssystem das Klagepatent verletze, sei sie nicht selber gegenüber der Klägerin hoheitlich tätig geworden. Weiter sei zu berücksichtigen, dass es Ziel des Patentgerichtsgesetzes sei, ein fachlich kompetentes Gericht über Streitigkeiten betreffend Nichtigkeit und Verletzung von Patenten entscheiden zu lassen; dies spreche dafür, dass das Bundespatentgericht für die vorliegende Streitigkeit zuständig sei, unabhängig davon, ob sich im konkreten Verfahren neben zivilrechtlichen allenfalls auch öffentlichrechtliche Fragen stellen. Den von der Beklagten erhobenen Einwand, die Nutzung der LSVA-Erhebungsinfrastruktur sei hoheitlicher Natur, weshalb es sich bei der erhobenen Klage um eine öffentlichrechtliche Streitigkeit handle, wies das Bundespatentgericht zurück. Bei der Erhebung der LSVA handle es sich zwar um eine öffentlichrechtliche Aufgabe, die nach Art. 85 BV der Finanzierung der Verkehrsinfrastruktur diene. Die Beklagte handle somit in Bezug auf die abgabepflichtigen Personen hoheitlich, und sie begründe dabei öffentlichrechtliche Schuldverhältnisse, die sich nicht nach dem Obligationenrecht, sondern nach dem Schwerverkehrsabgabegesetz richteten. Auch bei der LSVA-Erhebungsinfrastruktur handle es sich um ein öffentliches Werk, das sicherstelle, dass die Abgabe entsprechend Art. 85 BV und Art. 1 SVAG leistungsabhängig erhoben werden kann. Insgesamt sei die LSVA-Erhebungsinfrastruktur (einschliesslich der On-Board-Units) Teil des Verwaltungsvermögens der Beklagten und diene ausschliesslich öffentlichen Zwecken. Die Erhebung von Steuern und Abgaben durch die Beklagte, insbesondere die Veranlagung und der Bezug der LSVA, stellten reine Eingriffsverwaltung und damit öffentlichrechtliches Handeln der Beklagten dar. Demgegenüber seien die mit Lieferanten abgeschlossenen Verträge im Hinblick auf die konkrete Erhebung von Steuern und Abgaben privatrechtlich. Mit der Klägerin sei davon auszugehen, dass vorweg eine allfällige Patentverletzung durch die Herstellerfirmen der LSVA-Erhebungsinfrastruktur erfolgt sei, die betreffend das Klagepatent über keine Lizenzvereinbarung mit der Klägerin verfügt hätten; mithin sei eine allfällige Verletzung des Klagepatents durch die vertragsmässige Erstellung der Anlagen durch die privaten Herstellerfirmen erfolgt und finde allenfalls ihre Fortsetzung mit dem Betrieb der Anlagen durch die Beklagte. Das Bundespatentgericht hielt weiter dafür, es sei im zu beurteilenden Fall nicht von Bedeutung, dass die Beklagte gegenüber den abgabepflichtigen Personen hoheitlich auftritt; gegenüber der Klägerin sei sie nicht hoheitlich aufgetreten, indem sie etwa das Klagepatent enteignet hätte. Die Klägerin wiederum stütze sich auf das Ausschliesslichkeitsrecht gemäss Art. 8 PatG und leite gegenüber der Beklagten aus einer Verletzung des Klagepatents nach Art. 66 PatG zivilrechtliche Ansprüche ab. Sie trete der Beklagten damit aufgrund der von ihr behaupteten Patentverletzung - worauf im Sinne der doppelrelevanten Tatsachen allein abzustellen sei - als gleichgeordnetes Rechtssubjekt gegenüber. Ob die allenfalls verletzenden Handlungen der Beklagten auch gewerbsmässig im Sinne von Art. 8 Abs. 1 PatG seien, brauche (vorerst) nicht geprüft zu werden. Das Bundespatentgericht stellte fest, dass die von der Beklagten im Rahmen der LSVA-Erhebung wahrgenommenen öffentlichen Interessen und Aufgaben in einem Spannungsverhältnis zum Ausschliesslichkeitsrecht des Patentinhabers gemäss Art. 8 PatG stünden, der auf ein typisch privates Interesse gerichtet sei. Das Gericht wies insbesondere darauf hin, dass für die Beurteilung der sachlichen Zuständigkeit die von der Klägerin geltend gemachten Ansprüche massgeblich seien, die sich ausschliesslich auf das Patentgesetz stützten. Die Rechtsfolgen seien zivilrechtlicher Natur, womit im zu beurteilenden Fall von einer zivilrechtlichen Streitigkeit auszugehen sei. Zwar müssten etwa nach der bundesgerichtlichen Rechtsprechung zum Nachbarrecht privatrechtliche Abwehransprüche dem vorrangigen öffentlichen Interesse (z.B. Betrieb eines konzessionierten Flughafens) weichen und stünden die Unterlassungs-, Beseitigungs- und Schadenersatzansprüche gemäss Art. 679 ZGB nicht zur Verfügung; an deren Stelle trete ein Anspruch auf Entschädigung für die Enteignung der nachbarrechtlichen Abwehransprüche gemäss Art. 5 Abs. 1 des Enteignungsgesetzes. In Bezug auf die Enteignungsentschädigung für patentrechtliche Verletzungsansprüche bestehe jedoch keine entsprechende Bestimmung im Enteignungsgesetz. Damit verblieben der Beklagten die Rechtsbehelfe in Art. 32 und Art. 40 PatG; sie habe aber selber nicht behauptet, ein Enteignungsverfahren eingeleitet oder mit der Klägerin Verhandlungen betreffend eine Zwangslizenz geführt zu haben. Von der Beklagten sei überdies nicht dargetan und es lägen auch keine Gründe für eine entsprechende Annahme vor, dass im Patentgesetz eine Gesetzeslücke in Bezug auf eine entschädigungslose öffentlichrechtliche Eigentumsbeschränkung bestehe oder diese Lücke durch Analogieschluss aus anderen Gesetzen, insbesondere dem Enteignungsgesetz, gefüllt werden könnten. Daher sei auf die Klage einzutreten. C. Mit Beschwerde in Zivilsachen beantragt die Schweizerische Eidgenossenschaft dem Bundesgericht, es sei der Beschluss des Bundespatentgerichts vom 7. Juni 2012 aufzuheben, auf die Klage sei nicht einzutreten und es sei die Sache im Übrigen zur Verlegung der erstinstanzlichen Verfahrenskosten an das Bundespatentgericht zurückzuweisen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Die Vorinstanz hat auf eine Vernehmlassung verzichtet. Die Beschwerdeführerin hat dem Bundesgericht am 5. Oktober 2012 eine Replik, die Beschwerdegegnerin am 17. Oktober 2012 eine Duplik eingereicht.