Sachverhalt: A. Am 29. April 2015 beschloss der Regierungsrat des Kantons Zürich eine Änderung der kantonalen Bauverfahrensverordnung vom 3. Dezember 1997 (BVV; LS 700.6). Unter anderem soll danach § 1 BVV wie folgt neu gefasst werden: "Keiner baurechtlichen Bewilligung bedürfen in Bauzonen: a. Bauten und Anlagen, deren Gesamthöhe nicht mehr als 2,5 m beträgt und die eine Bodenfläche von höchstens 6 m2 überlagern; sie sind jedoch bewilligungspflichtig in Kernzonen, im Geltungsbereich einer anderen Schutzanordnung oder eines Ortsbild- oder Denkmalschutzinventars und im Bereich von Verkehrsbaulinien, lit. b-e unverändert. f. nicht leuchtende Eigenreklamen auf privatem Grund bis zu einer Fläche von 1⁄2 m2 je Betrieb; solche Anlagen sind jedoch bewilligungspflichtig in Kernzonen und im Geltungsbereich einer anderen Schutzanordnung oder eines Ortsbild- oder Denkmalschutzinventars, lit. g-i unverändert. lit. k wird aufgehoben." Ebenso ist eine Neufassung von Ziff. 1.2.4 des Anhangs zur BVV vorgesehen, der die Zuständigkeit für die Bewilligung von Bauten und Anlagen in besonderer Lage ausserhalb der Bauzonen regelt. Am 15. Mai 2015 erfolgte die Publikation im Amtsblatt des Kantons Zürich. Gegen den Beschluss des Regierungsrats erhoben A._ und die B._ AG Beschwerde beim Verwaltungsgericht des Kantons Zürich. Sie beantragten, der Beschluss sei in Bezug auf § 1 und Ziff. 1.2.4 des Anhangs zur BVV aufzuheben. Mit Urteil vom 3. Dezember 2015 wies das Verwaltungsgericht die Beschwerde ab, soweit es darauf eintrat (Dispositiv-Ziffer 1). Die Gerichtsgebühr bestimmte es auf Fr. 12'000.-- (Dispositiv-Ziffer 2) und auferlegte sie den Beschwerdeführern je zur Hälfte und unter solidarischer Haftung (Dispositiv-Ziffer 3). Zur Begründung führte es im Wesentlichen aus, dass die Unterscheidung zwischen "Bauzonen" und "anderen Zonen" gemäss n§ 1 BVV lediglich eine in Übereinstimmung mit übergeordnetem bestehendem Recht erfolgte Präzisierung bzw. Klarstellung und keine Verschärfung beinhalte. Auch in Bezug auf Ziff. 1.2.4 des revidierten Anhangs zur BVV sei nicht ersichtlich, inwieweit damit die bundes- und kantonalrechtlichen Zuständigkeitsordnungen verletzt würden. Die nun festgeschriebene kantonale Zuständigkeit sei bundesrechtlich verlangt und entspreche der bisherigen Praxis. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 29. Januar 2016 beantragen A._ und die B._ AG, Dispositiv-Ziffer 2 des verwaltungsgerichtlichen Urteils aufzuheben und die Gerichtsgebühr von Fr. 12'000.-- auf maximal Fr. 4'000.-- zu reduzieren. Eventualiter sei die Vorinstanz zu verpflichten, über die Höhe der Gerichtsgebühr neu zu befinden. Das Verwaltungsgericht beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Der Regierungsrat hat auf eine Vernehmlassung verzichtet. Die Beschwerdeführer halten in ihrer Stellungnahme dazu an ihren Anträgen und Rechtsauffassungen fest.