Sachverhalt:
A.
X._ ist Eigentümer der in der Landwirtschaftszone liegenden Parzelle Nr. 2055 in Brienz. Nordwestlich grenzt diese an die bewaldete Parzelle Nr. 122, die im Eigentum der Schwellenkorporation Aareboden steht.
Am 30. August 2004 reichte X._ bei der Einwohnergemeinde Brienz ein Baugesuch ein für die Umnutzung der bestehenden landwirtschaftlichen Halle in eine Lager- und Einstellhalle mit einer Werkstatt für den eigenen Gewerbebetrieb. Im Rahmen dieses Baubewilligungsverfahrens stellte er erstmals 2006 und nochmals im Jahr 2010 ein nachträgliches Rodungsgesuch für eine Zufahrt über Parzelle Nr. 122.
Gegen das Vorhaben erhob u.a. die Schwellenkorporation Aareboden Einsprache. Am 9. Dezember 2011 erteilte das Regierungsstatthalteramt Interlaken-Oberhasli die Baubewilligung und eröffnete die Ausnahmebewilligung für das Bauen ausserhalb der Bauzone gemäss Verfügung des Amts für Gemeinden und Raumordnung des Kantons Bern (AGR) vom 6. Juli 2009. Dagegen wies das Regierungsstatthalteramt das Rodungsgesuch ab und verpflichtete X._, die widerrechtlich erstellte Zufahrt auf Parzelle 122 zurückzubauen und das Gelände wieder aufzuforsten.
B.
Hiergegen erhob X._ erfolglos Beschwerde bei der Bau-, Verkehrs- und Energiedirektion des Kantons Bern (BVE) und anschliessend Beschwerde beim Verwaltungsgericht des Kantons Bern, mit dem Antrag, es sei auf die Wiederherstellung des rechtmässigen Zustands auf Parzelle Nr. 122 zu verzichten, und statt dessen sei er zu verpflichten, auf der Parzelle Nr. 3202 "Harstettli" eine Fläche von 324 m2 wieder aufzuforsten. Das Verwaltungsgericht wies die Beschwerde am 7. Januar 2013 ab, soweit es darauf eintrat.
C.
Dagegen hat X._ am 13. Februar 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht erhoben. Er beantragt, der angefochtene Entscheid sei aufzuheben und auf die Wiederherstellung des ursprünglichen Zustands sei zu verzichten.
D.
Die Schwellenkorporation Aareboden schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt Abweisung der Beschwerde, soweit darauf einzutreten sei. Die BVE hat auf eine Vernehmlassung verzichtet.
Das BAFU legt in seiner Vernehmlassung dar, dass die kantonalen Behörden nach Art. 50 Abs. 2 des Bundesgesetzes über den Wald vom 4. Oktober 1991 (WaG; SR 921.0) zur Beseitigung rechtswidriger Zustände und somit zur Anordnung der Wiederherstellung des rechtmässigen Zustands verpflichtet seien. Die vom Bundesgericht festgelegte Verwirkungsfrist von 30 Jahren (<ref-ruling> E. 6b S. 271) sei noch nicht abgelaufen; die Wiederherstellung könne auch in keiner Weise als unverhältnismässig betrachtet werden.
E.
In seiner Replik hält der Beschwerdeführer an seinen Anträgen fest.

Erwägungen:
1.
Da alle Sachurteilsvoraussetzungen vorliegen, ist auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten grundsätzlich einzutreten. Fraglich ist allerdings, ob nicht insoweit ein neues, nach Art. 99 Abs. 2 BGG unzulässiges Begehren vorliegt, als die Verpflichtung zur Ersatzaufforstung auf einer anderen Parzelle fallen gelassen wurde. Die Frage kann offen bleiben, wenn die Beschwerde ohnehin abzuweisen ist.
2.
Es ist unstreitig, dass die Rodung für die Erstellung der Zufahrtsstrasse nie bewilligt wurde und auch nachträglich nicht bewilligt werden kann. Unstreitig ist weiter, dass die - im vorliegenden Fall einschlägige - Verwirkungsfrist von 30 Jahren noch nicht abgelaufen ist. Streitig ist lediglich, ob besondere Gründe des Vertrauensschutzes vorliegen, die vorliegend eine Duldung des rechtswidrigen Zustands gebieten.
3.
Der Beschwerdeführer rügt zunächst, der Sachverhalt sei vom Verwaltungsgericht in mehreren Punkten offensichtlich unrichtig festgestellt worden.
3.1. Insbesondere treffe es nicht zu, dass die gerodete Waldfläche im Zeitpunkt des Augenscheins vom 30. November 1995 einen Umfang von bloss 8 m2 hatte und seither erheblich erweitert worden sei, zuerst auf 160 m2 und danach auf 342 m2 (E. 6.3 S. 12 des angefochtenen Entscheids). Dies beruhe auf einer Missinterpretation der Skizze von Oberförster A._ vom 2. Juni 1995. Vielmehr umfasse die Strasse ohne Böschung ca. 160 m2 und mit Böschung ca. 324 m2; seit 1995 sei keine zusätzliche Rodung vorgenommen worden. Dies ergebe sich aus Ziff. 4 der Aktennotiz vom 30. Juni 2005. Zudem beantragt der Beschwerdeführer erstmals die Edition gewisser Fotos zum Umfang der Rodung.
Die Beschwerdegegnerin und das Verwaltungsgericht (hinsichtlich der Fotos) machen geltend, es handle sich um unzulässige Noven.
3.1.1. Bereits im Verfahren vor der BVE hatte die Gemeinde Brienz, gestützt auf die Skizze von Oberförster A._ vom 2. Juni 1995, geltend gemacht, dass die Waldfläche von 324 m2 grösstenteils erst nach dem Augenschein vom 30. November 1995 gerodet worden sei, indem der Zufahrtsweg immer weiter nach Norden, in den Wald hinein, verschoben worden sei (Stellungnahme vom 8. Februar 2012); davon ging auch die BVE in ihrem Entscheid vom 20. April 2012 (E. 3d S. 10) aus. Insofern hätte der Beschwerdeführer bereits im Verfahren vor Verwaltungsgericht Anlass gehabt, Beweismittel zu dieser Frage zu benennen.
Der Antrag auf Edition von Fotos ist daher ein unzulässiges neues Beweismittel (Art. 99 Abs. 1 BGG). Dagegen ist die Aktennotiz vom 30. Juni 2005 nicht neu, da sie (wie auch der Amtsbericht vom 1. Mai 1998; vgl. dazu unten E. 3.2) von der Gemeinde Brienz vor der BVE eingereicht worden ist.
3.1.2. Auf der vom Oberförster A._ am 2. Juni 1995 angefertigten Skizze findet sich neben der schraffiert eingezeichneten illegal gerodeten Waldfläche für die Zufahrtsstrasse der Vermerk "ca. 4 x 2 m, 4 Bäume eingedeckt". Dies spricht dafür, dass die 1995 gerodete Fläche nur ca. 8 m2 betrug. Dafür spricht auch deren Bezeichnung als "Zufahrtssträssli" in der Aktennotiz vom 30. November 1995 und der Hinweis, dass Oberförster A._ Anzeige hätte erstatten müssen, wenn das Vergehen grösseren Ausmasses wäre. Hätte die Strasse schon damals 160 m2 bzw. (mit Böschung) 324 m 2 umfasst, wäre dies der Fall gewesen.
Aus Ziff. 4 der Aktennotiz vom 30. Juni 2005 ergibt sich lediglich, dass dem Förster, B._, der illegale Zustand seit längerer Zeit bekannt war und er der Auffassung war, man könnte (nach Durchführung eines Rodungsverfahrens) die heutige Situation von illegal auf geduldet ändern. Dagegen ergibt sich aus dieser Passage nichts zur Frage, ob nach 1995 noch Rodungen vorgenommen wurden.
In diesem Punkt erweist sich die Sachverhaltsfeststellung des Verwaltungsgerichts somit nicht als offensichtlich unrichtig.
3.2. Der Beschwerdeführer rügt weiter, das Verwaltungsgericht habe ihm zu Unrecht unterstellt, sich einzig auf die Aktennotiz vom 30. November 1995 berufen zu haben; tatsächlich sei die behördliche Zusicherung aus dem Jahr 1995 immer wieder bestätigt worden (1998, 2001 und 2005). Er beruft sich hierfür auf den Amtsbericht vom 1. Mai 1998 und die Aktennotizen vom 15. März 2001 und vom 30. Juni 2005.
Es trifft jedoch zu, dass sich der Beschwerdeführer in seiner Beschwerdeschrift vom 23. Mai 2012 ans Verwaltungsgericht (S. 5) zum Thema "Vertrauensgrundsatz" ausschliesslich auf die Aktennotiz vom 30. November 1995 berufen hat. Immerhin hat das Verwaltungsgericht (in E. 6.3 S. 12 des angefochtenen Entscheids) von sich aus geprüft, ob sich aus späteren, im Rahmen der Verhandlungen zwischen den Verfahrensbeteiligten gemachten Äusserungen, etwas zugunsten des Beschwerdeführers ableiten lasse, was es verneinte.
3.3. Der vom Verwaltungsgericht festgestellte Sachverhalt ist daher im Folgenden zugrunde zu legen (Art. 105 Abs. 1 BGG).
4.
Der Beschwerdeführer macht geltend, ihm sei bereits am Augenschein vom 30. November 1995 zugesichert worden, dass das Zufahrtssträssli bleiben könne, weil eine Aufhebung unverhältnismässig wäre. Mit Verfügung vom 6. Dezember 1995 habe die Gemeinde Brienz zwar angeordnet, dass der Waldrand zwischen den Parzellen Nrn. 122 und 2055 bleiben müsse, dagegen sei von einer Wiederherstellung des ursprünglichen Zustands abgesehen worden. Im Amtsbericht vom 1. Mai 1998 habe die Waldabteilung 1 Oberland Ost bestätigt, dass der Zufahrtsweg von den Grundeigentümern und dem Forstdienst toleriert werde, der beanspruchte Waldboden aber Waldareal im Sinne des Gesetzes bleibe. Am 15. März 2001 habe ein weiterer Augenschein stattgefunden; dabei habe der Förster festgestellt, dass die Schwellenkorporation einen Zaun zwischen Wald und Strasse erstellen müsse; damit seien Zustand und Bestand der Zufahrtsstrasse erneut bestätigt worden. Am 28. Juni 2005 habe schliesslich ein Augenschein im Zusammenhang mit dem Umnutzungsgesuch stattgefunden. Die Waldabteilung habe festgehalten, dass ihr der illegale Zustand seit längerem bekannt sei und dieser von illegal auf Duldung abgeändert werden könne. Hierzu müsse ein Rodungsverfahren durchgeführt werden; zwar müsse das Rodungsgesuch abgewiesen werden, man könne dann aber auf Wiederherstellungsmassnahmen verzichten. Erstmals 2006 habe die Beschwerdegegnerin Einsprache gegen das Rodungsgesuch erhoben; dies sei aufgrund ihres bisherigen Verhaltens treuwidrig gewesen. Es verletze den Vertrauensschutz und sei unverhältnismässig, nach 25 Jahren die Beseitigung einer Strasse zu verlangen, mit deren Verbleib alle Beteiligten, einschliesslich der Waldeigentümerin, einverstanden gewesen seien.
4.1. Der Beschwerdeführer bezeichnet die Aktennotiz vom 15. März 2001 selbst als Novum (Beschwerde S. 5); als solches kann es nach dem oben (E. 3.1.1) Gesagten nicht berücksichtigt werden (anders als der von der Gemeinde Brienz vor der BVE eingereichte Amtsbericht vom 1. Mai 1998).
4.2. Das Verwaltungsgericht ging davon aus, das von der Gemeinde 1995 signalisierte Entgegenkommen in Bezug auf die Wiederherstellung könne nicht als vorbehaltlose Zusicherung verstanden werden, sondern nur dahingehend, dass auf eine Wiederherstellung gegebenenfalls hätte verzichtet werden können, wenn der Beschwerdeführer sich im Übrigen vollumfänglich an die Weisungen der Gemeinde gehalten hätte. Dies sei jedoch nicht der Fall gewesen; im Gegenteil habe der Beschwerdeführer die für die Zufahrtsstrasse gerodete Fläche erheblich erweitert. Auch aus den späteren Äusserungen könne der Beschwerdeführer nichts zu seinen Gunsten ableiten: So habe der Regierungsstatthalter dem Beschwerdeführer nach mehreren Einigungsverhandlungen mit Schreiben vom 6. März 2008 eine Wiederherstellungsverfügung durch die Gemeinde in Aussicht gestellt, sofern er die Zufahrtsverhältnisse nicht klären könne. Dies sei jedoch in der Folge nicht geschehen. Unter diesen Umständen habe der Beschwerdeführer aus dem Verhalten der Gemeinde allenfalls eine Duldung auf Zusehen hin, aber keinen Vertrauenstatbestand ableiten können.
4.3. Diese Erwägungen sind aus bundesrechtlicher Sicht nicht zu beanstanden. Ergänzend ist darauf hinzuweisen, dass der Beschwerdeführer selbst nicht geltend macht, im Vertrauen auf die angebliche Zusicherung der Gemeinde irgendwelche Dispositionen getroffen zu haben, die er nicht (oder nur schwer) wieder rückgängig machen könne.
Hinzu kommt, dass sich die Zufahrtsstrasse auf fremdem Grund befindet. Zwar wurde diese von der Beschwerdegegnerin als Waldeigentümerin eine Zeit lang toleriert (so Aktennotiz vom 1. Mai 1998) und fanden Verhandlungen im Hinblick auf die Vornahme eines Landabtauschs oder die Einräumung eines Baurechts statt (vgl. Protokoll der Einigungsverhandlung vom 18. Juni 2007 S. 3 f.). Nachdem diese Verhandlungen gescheitert waren, war es jedoch keinesfalls treuwidrig, wenn die Beschwerdegegnerin ihre Unterschrift unter das Rodungsgesuch verweigerte und die Wiederherstellung des rechtmässigen Zustands verlangte.
4.4. Schliesslich ist auch keine Verletzung des Verhältnismässigkeitsprinzips ersichtlich. Hierfür kann auf die zutreffenden Erwägungen des Verwaltungsgerichts (angefochtener Entscheid E. 7) verwiesen werden. Hinzu kommt, dass der Bereich hinter der Lagerhalle problemlos von Süden her über die Parzelle des Beschwerdeführers erschlossen werden kann (vgl. Entscheid BVE E. 3b S. 8) und dieser selbst ein Bau- und Transportgewerbe betreibt, weshalb sich die finanzielle Belastung der Wiederherstellung in Grenzen hält (vgl. Gesamtbauentscheid E. 8 S. 10).
5.
Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 und 68). Da die Beschwerdegegnerin nicht in ihrer Funktion als Schwellenkorporation, sondern als Waldeigentümerin wie eine Privatperson betroffen wurde, rechtfertigt es sich, ihr eine Parteientschädigung zuzusprechen (Art. 68 Abs. 3 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieser hat die Schwellenkorporation Aareboden für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, der Bau-, Verkehrs- und Energiedirektion des Kantons Bern, dem Verwaltungsgericht des Kantons Bern, Verwaltungsrechtliche Abteilung, und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 17. September 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Aemisegger
Die Gerichtsschreiberin: Gerber