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 <ref-law> (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.

Erwägungen:
1.
1.1. Das Verwaltungsgericht hat als letzte kantonale Instanz (<ref-law>) in einer Angelegenheit des öffentlichen Rechts entschieden (<ref-law>). Ein Ausnahmegrund liegt nicht vor (<ref-law>). Betreffend den Abschnitt 1 hiess die Vorinstanz die Beschwerde teilweise gut und wies die Sache im Sinne der Erwägungen zur Neubeurteilung an den Regierungsrat zurück. Bezüglich des Abschnitts 2 wies die Vorinstanz die Beschwerde hingegen ab. Es wird damit ein Teil des Streitgegenstands abschliessend geregelt, womit ein Teilentscheid vorliegt (<ref-law>), gegen den die Beschwerde zulässig ist (vgl. auch Urteil 1C_355/2008 vom 28. Januar 2009 E. 1.2).
1.2. Der Bundesgesetzgeber hat für verschiedene Gebiete - vorab im Umweltrecht - abstrakte Beschwerderechte für Organisationen geschaffen (vgl. <ref-law>). Die Voraussetzungen des Beschwerderechts richten sich ausschliesslich nach den jeweiligen Vorschriften. Die allgemeinen Voraussetzungen von <ref-law> kommen nicht zur Anwendung, d.h. die Organisationen müssen weder ein schutzwürdiges persönliches Interesse nachweisen, noch die Wahrung der Interessen ihrer Mitglieder geltend machen (Bernhard Waldmann, Kommentar BGG, 2. Aufl. 2011, Art. 89 N. 69).
Das Vorhaben erforderte eine Umweltverträglichkeitsprüfung (<ref-law>). Der VCS und der WWF Schweiz gehören zu den gesamtschweizerischen Organisationen, die nach <ref-law> zur Erhebung von Beschwerden ans Bundesgericht berechtigt sind (<ref-law>); der WWF Schweiz ist überdies nach <ref-law> (SR 451) zur Beschwerdeführung befugt (vgl. Anhang der Verordnung vom 27. Juni 1990 über die Bezeichnung der im Bereich des Umweltschutzes sowie des Natur- und Heimatschutzes beschwerdeberechtigten Organisationen [VBO; SR 814.076]).
Sowohl <ref-law> als auch <ref-law> sehen vor, dass das Beschwerderecht den Organisationen nur für Rügen in Rechtsbereichen zusteht, die seit mindestens zehn Jahren Gegenstand ihres statutarischen Zwecks bilden. Die Beschwerdeführer rügen Bestimmungen des RPG (SR 700) und des kantonalen Richtplans und damit in Zusammenhang stehend <ref-law> als verletzt. Das Beschwerderecht der Umweltschutzorganisationen steht im Dienst der Respektierung sämtlicher bundesrechtlicher Vorschriften über den Schutz der Umwelt, wozu auch die Anliegen der Raumplanung zählen (<ref-ruling> E. 1c S. 304 f.; Urteil 1C_283/2012 vom 2. April 2014 E. 1.3, nicht publ. in: <ref-ruling>). Die vorgebrachten Rügen erweisen sich als zulässig.
Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist einzutreten.
2.
Umstritten ist im zu beurteilenden Fall, ob die mit dem Vorhaben verbundene Verminderung der Fruchtfolgeflächen einen Richtplanbeschluss des Grossen Rats des Kantons Aargau voraussetzt.
2.1. Der kantonale Richtplan vom 20. September 2011 (vgl. Grossratsbeschluss über den kantonalen Richtplan vom 20. September 2011 [SAR 713.140]) enthält im Kapitel L 3.1 (Landwirtschaftsgebiet und Fruchtfolgeflächen) zu den Fruchtfolgeflächen unter anderem folgende Planungsanweisung:
Die Verminderung der Fruchtfolgeflächen um mehr als 3 ha pro Planung und Vorhaben setzt einen Richtplanbeschluss voraus.
2.2. Die Vorinstanz hat erwogen, das genehmigte Strassenbauprojekt nehme gemäss Richtplangesamtkarte Fruchtfolgeflächen im Abschnitt 1 und 2 in Anspruch. Die Planungsanweisung im Richtplan sei klar, nämlich, dass eine Verminderung der Fruchtfolgeflächen um mehr als 3 ha "pro Planung oder Vorhaben" einen Richtplanbeschluss voraussetze. Massgebend sei mithin eine Gesamtbetrachtung, was für das vorliegende Strassenbauvorhaben bedeute, dass 3,12 ha Fruchtfolgeflächen beansprucht würden (Abschnitt 1: 1,32 ha; Abschnitt 2: 1,8 ha). Das Vorhaben setze daher einen entsprechenden Richtplanbeschluss voraus. Ein solcher fehle indes. Der Beschluss des Grossen Rats vom 8. Januar 2008 habe zwar die Festsetzung der Umfahrung Mellingen im Richtplan betroffen. Der Botschaft des Regierungsrats vom 5. September 2007 könne jedoch entnommen werden, dass der Bedarf an Fruchtfolgeflächen noch nicht genau angegeben werden könne, jedenfalls aber unter dem Grenzwert von 3 ha liegen werde. Der Beschluss des Grossen Rats vom 16. November 2010 habe sodann den Grosskredit für die Umfahrung Mellingen und die Anpassung des Kantonsstrassennetzes betroffen. Bezüglich der Fruchtfolgeflächen sei in der Botschaft des Regierungsrats vom 1. September 2010 festgehalten worden, der Verbrauch betrage ca. 2,7 ha, wobei bei der weiteren Projektbearbeitung Optimierungen bzw. Massnahmen zur Verringerung der Beeinträchtigungen erarbeitet würden. Von einer Verminderung der Fruchtfolgeflächen im Umfang von über 3 ha sei somit in keinem der beiden genannten Beschlüsse ausgegangen worden.
Gestützt auf das eingeholte ENHK-Gutachten sei zudem im Abschnitt 1 eine Verschiebung der Linienführung nach Osten in die Landwirtschaftszone geplant, weshalb es voraussichtlich zu einer weiteren Verminderung der Fruchtfolgeflächen kommen werde. Ein entsprechender Richtplanbeschluss erweise sich damit umso mehr als notwendig (vgl. zum Ganzen angefochtenes Urteil E. 3.2.2).
2.3. Die Beschwerdeführer machen geltend, sie hätten im vorinstanzlichen Verfahren unter anderem die fehlende, für das Vorhaben aber notwendige Richtplananpassung betreffend Fruchtfolgeflächen gemäss kantonalem Richtplan beanstandet. Diese Rüge betreffe sowohl den Abschnitt 1 als auch den Abschnitt 2 (Abschnitt 1: 1,32 ha; Abschnitt 2: 1,8 ha). Obwohl die Vorinstanz das Vorbringen ausdrücklich als begründet eingestuft habe (angefochtenes Urteil E. 3.2.2), habe sie die Beschwerde in Bezug auf den Abschnitt 2 in der Folge abgewiesen. Damit leide das angefochtene Urteil an einem unauflösbaren Widerspruch, was gegen <ref-law> verstosse. Zudem verletze eine Nutzungsplanung respektive eine Baubewilligung ohne Richtplangrundlage die in Art. 2 RPG vorgeschriebene Planungspflicht bzw. den planerischen Stufenbau.
2.4. Das BVU/AG bestreitet in seiner Vernehmlassung im bundesgerichtlichen Verfahren die Feststellungen der Vorinstanz nicht, bringt jedoch insbesondere vor, der Richtplantext, wonach die Verminderung der Fruchtfolgeflächen um mehr als 3 ha pro Planung oder Vorhaben einen Richtplanbeschluss voraussetze, schliesse die Anwendung des sog. Nettoprinzips nicht aus. Entscheidend sei die Nettofläche des Verlusts an Fruchtfolgeflächen. Es sei daher insbesondere zulässig, dass ein Vorhaben durch gleichwertige qualitative Bodenaufwertung die Beanspruchung von Fruchtfolgeflächen reduziere. Der Regierungsrat plane im Zusammenhang mit der im Januar 2016 öffentlich aufgelegten Projektänderung zum Abschnitt 1 Aufwertungsflächen festzulegen, die mit der Realisierung der Umfahrung zu gleichwertigen Fruchtfolgeflächen ausgestaltet werden sollten. Eine entsprechende Projektergänzung solle sobald wie möglich öffentlich aufgelegt werden. Durch die geplanten Flächenaufwertungen werde sich die Verminderung der Fruchtfolgeflächen auf insgesamt unter 3 ha reduzieren, womit sich ein Richtplanbeschluss des Grossen Rats erübrige.
Die Projektgenehmigung sei mit der Nebenbestimmung (Bedingung) zu versehen, dass vor Baubeginn ein gleichwertiger Ersatz an Fruchtfolgeflächen für die 3 ha übersteigende Beanspruchung rechtskräftig verfügt sein müsse.
2.5. Das kantonale Recht sieht ausdrücklich vor, dass die Verminderung der Fruchtfolgeflächen um mehr als 3 ha einen Richtplanbeschluss des Grossen Rats voraussetzt. Ein solcher liegt, wie die Vorinstanz aufgezeigt hat, nicht vor (vgl. E. 2.2 hiervor). Das BVU/AG wendet, wie dargelegt, ein, der Verlust der Fruchtfolgeflächen werde nach dem Nettoprinzip berechnet und mit den vorgesehenen Aufwertungsflächen werde der Saldo unter 3 ha zu liegen kommen, sodass sich ein Grossratsbeschluss erübrige (vgl. E. 2.4 hiervor).
Ob diese Auslegung der Planungsanweisung im kantonalen Richtplan durch das BVU/AG bundesrechtskonform ist, kann vorliegend offen gelassen werden. Jedenfalls müsste, wenn sich ein Richtplanbeschluss des Grossen Rats erübrigen sollte, eine genaue Saldo-Berechnung des Fruchtfolgeflächenverlusts mit planerischer Festlegung der Aufwertungsflächen und der Verpflichtung zur Aufwertung bei der Genehmigung des Projekts durch den Regierungsrat vorliegen und in den Genehmigungsbeschluss aufgenommen werden. Dies ist unbestrittenermassen nicht erfolgt; vielmehr ist eine entsprechende Flächenaufwertung erst in Planung.
Da die Abschnitte 1 und 2 als ein Gesamtvorhaben ("Umfahrung Mellingen") zu betrachten sind und für beide Abschnitte Fruchtfolgeflächen in Anspruch genommen werden, hätten beide Abschnitte von der Vorinstanz zur Überarbeitung der Planung an den Regierungsrat zurückgewiesen werden müssen. Indem die Vorinstanz die Beschwerde der Beschwerdeführer betreffend den Abschnitt 2 abgewiesen hat, obwohl hinsichtlich der Fruchtfolgeflächenreduktion eine Genehmigungsvoraussetzung fehlte (Grossratsbeschluss oder allenfalls Berechnung des Nettoverlusts an Fruchtfolgeflächen unter Festlegung der Aufwertungsflächen), hat sie die Vorgaben des kantonalen Richtplans in willkürlicher Weise missachtet. Zugleich hat sich die Vorinstanz mit der teilweisen Abweisung der Beschwerde in einen unauflösbaren Widerspruch zu ihrer zutreffenden Begründung gesetzt, was ebenfalls gegen <ref-law> verstösst.
2.6. Ob die Vorinstanz dem Mangel, wie vom BVU/AG in seiner Stellungnahme im bundesgerichtlichen Verfahren vorgebracht, mit einer Nebenbestimmung (Bedingung) zum 2. Abschnitt hätte abhelfen können, braucht nicht entschieden zu werden, da die Vorinstanz keine solche Nebenbestimmung in ihr Urteil aufgenommen hat. Mit Dispositivziffer 3 wird einzig angeordnet, dass mit dem Bau des Abschnitts 2 erst begonnen werden darf, wenn der Abschnitt 1 rechtskräftig bewilligt ist. Die Festlegung des Fruchtfolgeflächenverbrauchs beschlägt indes nicht nur den Abschnitt 1, sondern betrifft auch den Abschnitt 2, weshalb die Genehmigung für diesen Abschnitt nicht hätte bestätigt werden dürfen.
3.
Die Beschwerde ist nach dem Gesagten gutzuheissen. Dispositivziffern 2, 4 und 5 des Urteils der Vorinstanz vom 26. November 2015 sowie der Genehmigungsentscheid des Regierungsrats des Kantons Aargau vom 20. März 2013 betreffend Abschnitt 2 (Entscheid Nr. 2013-000322) und der Einwendungsentscheid des Regierungsrats vom 20. März 2013 (Entscheid Nr. 2013-000319), soweit den Abschnitt 2 betreffend, sind antragsgemäss aufzuheben. Die Sache ist zu neuem Entscheid im Sinne der Erwägungen an den Regierungsrat und zur Neuregelung der Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens an die Vorinstanz zurückzuweisen.
Dem Ausgang des bundesgerichtlichen Verfahrens entsprechend sind keine Gerichtskosten zu erheben (<ref-law>). Der Kanton Aargau hat den Beschwerdeführern eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Dispositivziffern 2, 4 und 5 des Urteils des Verwaltungsgerichts des Kantons Aargau vom 26. November 2015 sowie der Genehmigungsentscheid des Regierungsrats des Kantons Aargau vom 20. März 2013 betreffend Abschnitt 2 (Entscheid Nr. 2013-000322) und der Einwendungsentscheid des Regierungsrats vom 20. März 2013 (Entscheid Nr. 2013-000319), soweit den Abschnitt 2 betreffend, werden aufgehoben. Die Sache wird zu neuem Entscheid im Sinne der Erwägungen an den Regierungsrat und zur Neuregelung der Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Aargau hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit insgesamt Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Beschwerdeführern, dem Kanton Aargau, dem Regierungsrat des Kantons Aargau, dem Verwaltungsgericht des Kantons Aargau, 3. Kammer, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 13. Oktober 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Stohner