Conservation of charge holds.
When the plates are connected, one of the paired plates has a positive charge while the other a negative charge. This is true for both of the pairs that are connected. Unlike charges will meet and annihilate via the available conduction paths leaving the net sum the same, hence conservation of the net charge.
Note that (usually) on a charged capacitor the two plates carry equal but opposite charges. Hence the net charge on the device as a whole is zero. When we talk about the charge on a capacitor, we typically refer to the magnitude of the charge on one plate, since both plates have the same charge but of opposite sign. When charged capacitors are connected in parallel, the charges on the connected plates sum. If the charge signs are opposite, they will combine and cancel until no differently signed charges are left. Whatever un-combined charges are left represents the net remaining charge on that plate.