Sachverhalt: A. Das Vorhaben "NK 268 Umfahrung Mellingen" ist in zwei separate Projekte gegliedert: Der Abschnitt 1 umfasst die Neuanlage der Kantonsstrasse auf einer Länge von 1'030 m von der Birrfeldstrasse (K 269) bis zum Kreisel Tanklager (K 268) mit neuem Reussübergang inklusive flankierenden Massnahmen und die zur Umweltverträglichkeit erforderlichen Ausgleichs- und Ersatzmassnahmen. Damit wird der Altstadtkern Mellingen vom Durchgangsverkehr entlastet. Der Abschnitt 2 umfasst auf einer Länge von 950 m die Umfahrung des Siedlungsgebiets Mellingen von der Birrfeldstrasse (K 269) bis zur Lenzburgerstrasse (K 268) inklusive flankierenden Massnahmen und die zur Umweltverträglichkeit erforderlichen Ausgleichs- und Ersatzmassnahmen. Der Abschnitt 2 entlastet hauptsächlich die Birrfeldstrasse vom Durchgangsverkehr durch den Innerortsabschnitt von Mellingen. Am 3. Juli 2012 erhoben unter anderem der Verkehrs-Club der Schweiz (VCS) und der WWF Schweiz Einwendungen gegen die öffentlich aufgelegten Bauprojekte. Mit Entscheid vom 20. März 2013 wies der Regierungsrat des Kantons Aargau die Einwendungen des VCS und des WWF Schweiz mehrheitlich ab (Entscheid Nr. 2013-000319). Gleichentags genehmigte der Regierungsrat die Bauprojekte für die Abschnitte 1 und 2 gestützt auf § 95 des kantonalen Gesetzes vom 19. Januar 1993 über Raumentwicklung und Bauwesen (Baugesetz, BauG/AG; SAR 713.100) und Art. 10a USG (SR 814.01) als rechtmässig und umweltverträglich, unter verschiedenen Änderungen, Auflagen und Bedingungen (Entscheide Nrn. 2013-000321 und 2013-000322). Am 6. Mai 2013 erhoben der VCS und der WWF Schweiz Verwaltungsgerichtsbeschwerde an das Verwaltungsgericht des Kantons Aargau. Dieses holte unter anderem ein Gutachten bei der Eidgenössischen Natur- und Heimatschutzkommission (ENHK) ein (Gutachten vom 13. Februar 2015). Am 26. November 2015 entschied das Verwaltungsgericht Folgendes (Entscheid Nr. WBE.2013.255) : 1. In teilweiser Gutheissung der Beschwerde werden der Genehmigungsentscheid des Regierungsrats vom 20. März 2013 betreffend Abschnitt 1 (Nr. 2013-000321) und der Einwendungsentscheid des Regierungsrats vom 20. März 2013 (Nr. 2013-000319), soweit er Abschnitt 1 betrifft, aufgehoben. Die Sache wird an den Regierungsrat zurückgewiesen zu neuer Entscheidung im Sinne der Erwägungen. 2. Im Übrigen wird die Beschwerde abgewiesen (bezüglich Genehmigungsentscheid des Regierungsrats vom 20. März 2013 betreffend Abschnitt 2 [Nr. 2013-000322] und Einwendungsentscheid des Regierungsrats vom 20. März 2013 [Nr. 2013-000319], soweit er Abschnitt 2 betrifft). 3. Mit dem Bau des Abschnitts 2 darf nicht begonnen werden, bevor der Abschnitt 1 rechtskräftig bewilligt ist. 4. Die verwaltungsgerichtlichen Verfahrenskosten, bestehend aus einer Staatsgebühr von Fr. 10'000.00 sowie der Kanzleigebühr und den Auslagen von Fr. 1'513.00, gesamthaft Fr. 11'513.00, sind von den Beschwerdeführern zur Hälfte mit Fr. 5'756.50 unter solidarischer Haftbarkeit zu bezahlen. Die restlichen Verfahrenskosten trägt der Staat. 5. Es werden keine Parteikosten ersetzt. 6. [Mitteilungen]. B. Mit Eingabe vom 1. Februar 2016 führen der VCS und der WWF Schweiz Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht mit den folgenden Anträgen: 1. Es sei in Gutheissung der Beschwerde Dispositivziffer 2 des vorinstanzlichen Urteils vom 26. November 2015 (WBE.2013.255) aufzuheben. 2. Es seien die von den Beschwerdeführern vor der Vorinstanz angefochtenen erstinstanzlichen Entscheide RRB Nr. 2013-000322 vom 20. März 2013 betreffend den Abschnitt 2 des Vorhabens "NK 268 Umfahrung Mellingen", und, damit verbunden, RRB Nr. 2013-000319, soweit inhaltlich den Abschnitt 2 des Vorhabens betreffend, aufzuheben und damit die Genehmigung für den Projektabschnitt 2 aufzuheben. 3. Eventualiter sei die Sache zur Neubeurteilung im Sinne der Erwägungen gemäss der nachfolgenden Begründung an die Vorinstanz bzw. die Erstinstanz zurückzuweisen. 4. Es seien die Dispositivziffern 4 und 5 aufzuheben und die Sache im Sinne der Erwägungen zur Neuverlegung der Kosten des vorinstanzlichen Verfahrens und zur Zusprechung einer Parteientschädigung an die Beschwerdeführer im vorinstanzlichen Verfahren an die Vorinstanz zurückzuweisen. 5. Alles unter Kosten- und Entschädigungsfolgen zulasten des Beschwerdegegners. Das Departement Bau, Verkehr und Umwelt des Kantons Aargau (BVU/AG) beantragt namens des Regierungsrats, auf die Beschwerde sei nicht einzutreten. Das Verwaltungsgericht stellt Antrag auf Beschwerdeabweisung. Das Bundesamt für Raumentwicklung ARE verzichtet auf eine Stellungnahme. Die Beschwerdeführer halten an ihrem Standpunkt und an ihren Anträgen fest.