Sachverhalt: A. Die Y._ AG (Beschwerdegegnerin) ist ein auf Vermittlung von Werbung und Sponsoring im Sportbereich spezialisiertes Unternehmen. Die Stade de Suisse Wankdorf Nationalstadion AG (Beschwerdeführerin) vermarktet und betreibt das ehemalige Wankdorfstadion in Bern als Nationalstadion. Die Parteien arbeiteten seit 1999 zusammen. Am 26. November 2003 schlossen sie einen Vermarktungsvertrag (Vermarktungsvertrag I) ab, den die Beschwerdeführerin im November 2005 kündigte. Indem die Parteien am 4./7. April 2006 einen in verschiedenen Punkten abgeänderten Vermarktungsvertrag (Vermarktungsvertrag II) schlossen, legten sie ihre Meinungsverschiedenheiten bei. Im Vermarktungsvertrag II räumte die Beschwerdeführerin der Beschwerdegegnerin diverse Rechte zur exklusiven und nicht-exklusiven Vermarktung von Werbeflächen und Werbemitteln im Stade de Suisse Wankdorf Bern ein. Während die Beschwerdegegnerin der Beschwerdeführerin für die exklusiven Rechte eine Pauschalentschädigung pro Saison zu entrichten hatte, stand ihr für die nicht-exklusiven Rechte ein Provisionsanspruch zu. Die Beschwerdeführerin löste den Vermarktungsvertrag II am 5. März 2007 per 30. Juni 2007 ausserterminlich unter Berufung auf "wichtige Gründe" auf, nachdem die Beschwerdegegnerin infolge Streitigkeiten ein gerichtliches Verfahren eingeleitet hatte. B. Die Beschwerdegegnerin erachtete die Kündigung als unzulässig und erhob im Mai 2007 Klage beim Handelsgericht des Kantons Bern. Sie machte gegenüber der Beschwerdeführerin sowohl Ansprüche für die Saison 2006/07 als auch Schadenersatz für entgangenen Gewinn in der Höhe von Fr. 1'900'800.-- für die Saison 2007/08 geltend. Die Beschwerdeführerin wandte ein, die Beschwerdegegnerin habe den Vermarktungsvertrag II mehrfach in schwerer Weise verletzt. Sie warf ihr unter anderem ungenügende Vermarktung (Underperformance) sowie eine daraus resultierende Verschlechterung der Attraktivität der Beschwerdeführerin für potentielle Werbekunden vor. Zudem habe die Beschwerdegegnerin die zugesicherte Professionalität und Sorgfalt sowie weitere vertragliche Vermarktungsgrundsätze verletzt. Die vorzeitige Auflösung des Vertragsverhältnisses sei somit berechtigt gewesen. Die Parteien schlossen hinsichtlich der Saison 2006/07 einen Vergleich ab, worauf die Beschwerdegegnerin die entsprechenden Rechtsbegehren zurückzog. Das Handelsgericht schrieb die Klage diesbezüglich als erledigt ab. Mit Bezug auf die Schadenersatzforderung für die Saison 2007/08 hiess das Handelsgericht die Klage mit Urteil vom 3. März 2009 im Umfang von Fr. 1'100'000.-- gut. C. Mit Beschwerde in Zivilsachen beantragt die Beschwerdeführerin dem Bundesgericht, das Urteil des Handelsgerichts aufzuheben und die Klage abzuweisen. Eventualiter sei der Schadenersatz neu zu bemessen, subeventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Das Gesuch der Beschwerdeführerin um aufschiebende Wirkung wies das Bundesgericht ab. Die Beschwerdegegnerin schliesst auf kostenfällige Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.