Sachverhalt: A. A.a. X._ (Kläger) und die deutsche Y._ GmbH & Co. KG (Beklagte, Beschwerdegegnerin) haben am 3./4. Mai 2007 eine als Mietvertrag bezeichnete Vereinbarung abgeschlossen, mit welcher sich der Kläger verpflichtete, der Beklagten das sich noch in der Projektierungsphase befindliche Gartencenter in L._ zu vermieten, währenddem die Beklagte die Verpflichtung einging, dem Kläger für die entsprechende Vermietung einen jährlichen Nettomietzins in der Höhe von 7 % der Anlagekosten zu bezahlen. Als minimale Mietdauer wurde dabei eine Zeit von zwanzig Jahren vereinbart, beginnend mit der Fertigstellung bzw. mit dem Tag der Eröffnung des noch zu errichtenden Gartencenters, spätestens aber mit dem Ablauf von neun Monaten seit Vorliegen der rechtskräftigen Baubewilligung. Des Weiteren wurde in der Vereinbarung vom 3./4. Mai 2007 festgehalten, dass diese unter der Bedingung der Erteilung einer rechtskräftigen Baubewilligung für das noch zu errichtende Gartencenter stehe, dass die Erstellung des entsprechenden Gartencenters nach den Vorgaben der Beklagten zu erfolgen habe und dass die Einzelheiten für die Erstellung des entsprechenden Gartencenters in einem noch abzuschliessenden Generalunternehmervertrag zu regeln seien. In der am 3. Mai 2007 abgeschlossenen Zusatzvereinbarung hielten die Parteien fest, dass der Kläger für die Realisierung des projektierten Gartencenters noch das notwendige Grundstück zu erwerben habe und dass gemäss den Bauvorschriften der Gemeinde Pratteln für die Realisierung des geplanten Gartencenters ein Quartierplanverfahren durchzuführen sei. Sowohl die Vereinbarung vom 3./4. Mai 2007 als auch die Zusatzvereinbarung vom 3. Mai 2007 wurden seitens der Beklagten vom damaligen Geschäftsführer Z._ unterzeichnet. Am 4. Mai 2007 schloss der Kläger mit der D._ AG in Liquidation einen bedingten Kaufvertrag über die Parzelle Nr. qqq, auf der das Gartencenter errichtet werden sollte. A.b. Am 26. März 2009 teilte Z._ dem Kläger mit einem entsprechenden und auf dem Briefpapier der Beklagten verfassten Schreiben mit, dass die Beklagte nach einer sehr langen Konferenz die Entscheidung getroffen habe, den geplanten Auftritt in der Schweiz aus wirtschaftlichen Gründen abzusagen (Absage des "Schweiz-Auftritts"). A.c. Mit Schreiben vom 26. August 2009 teilte der Kläger gestützt auf Art. 97 und Art. 107 Abs. 2 OR Verzicht auf die Erfüllung mit und forderte Schadenersatz wegen Nichterfüllung des Mietvertrages vom 3./4. Mai 2007 und der Zusatzvereinbarung vom 3. Mai 2007. Am 3. November 2009 erklärte der Kläger gegenüber dem Konkursamt Liestal den Rücktritt vom Kaufvertrag mit der D._ AG in Liquidation. In einer weiteren Vereinbarung zwischen der D._ AG in Liquidation und der E._ AG sowie mit Zustimmung des Klägers wurde der Kaufvertrag über das Grundstück am 27./30. November 2009 aufgehoben und die Liegenschaft neu der E._ AG verkauft. Die Beklagte erklärte ihrerseits mit Schreiben vom 22. Dezember 2009 den Rücktritt vom Mietvertrag vom 3./4. Mai 2007 und von der Zusatzvereinbarung vom 3. Mai 2007. Das geplante Gartencenter wurde in der Folge nie realisiert. B. B.a. Nach erfolgloser Schlichtung gelangte der Kläger mit Klage vom 31. März 2010 an das Bezirksgericht Liestal, indem er darum ersuchte, die Beklagte unter Vorbehalt einer Nachklage zu verurteilen, ihm einen Betrag von Fr. 6'500'000.-- nebst Zins zu 5 % seit dem 11. Dezember 2009 zu bezahlen. Die Beklagte beantragte die Abweisung der Klage und beantragte widerklageweise, der Kläger sei zu verurteilen, ihr unter Vorbehalt einer Mehrforderung einen Betrag von Fr. 218'503.50 nebst Zins zu 5 % seit dem 11. Dezember 2009 zu bezahlen. Mit Urteil des Gerichtspräsidenten des Bezirksgerichts Liestal vom 6. September 2012 wurden die Klage und die Widerklage abgewiesen. B.b. Gegen dieses Urteil erhoben die Rechtsnachfolger des am 17. Dezember 2012 verstorbenen Klägers - die Erbengemeinschaft X._, bestehend aus: A._, B._ und C._ (Beschwerdeführer) - Berufung an das Kantonsgericht Basel-Landschaft. Sie beantragten die Aufhebung des angefochtenen Urteils, die Verpflichtung der Beklagten zur Zahlung von Fr. 6'500'000.-- nebst Zins unter Nachklagevorbehalt, die Abweisung der Widerklage und eventualiter die Rückweisung der Sache an das Bezirksgericht zum Neuentscheid. Die Beklagte beantragte die Abweisung der Berufung und die Bestätigung des erstinstanzlichen Urteils, eventualiter bei Gutheissung von Ziffer 1 der Berufung die Rückweisung der Angelegenheit an das Bezirksgericht Liestal. Mit Entscheid vom 18. Juni 2013 wies das Kantonsgericht Basel-Landschaft die Berufung ab. C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführer dem Bundesgericht, der Entscheid des Kantonsgerichts Basel-Landschaft vom 18. Juni 2013 sei aufzuheben, es sei festzustellen, dass der von den Parteien abgeschlossene Mietvertrag vom 3./4. Mai 2007 wirksam ist, und die Sache sei zur Fortsetzung des Verfahrens an den Gerichtspräsidenten am Bezirksgericht Liestal, eventualiter an das Kantonsgericht Basel-Landschaft zurückzuweisen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz beantragt unter Hinweis auf die Begründung des angefochtenen Entscheids die Abweisung der Beschwerde. Die Beschwerdeführer haben unaufgefordert eine Replik, die Beschwerdegegnerin eine Duplik eingereicht. 