It sounds like your batteries aren't properly buffering the MPPT output. With the MPPT off, do your accessories still work off the batteries (even momentarily)? If not, you may have a bad cell or open battery fuse.
With healthy batteries connected in parallel to your MPPT, the voltage shouldn't vary more than a few tenths of a volt with a constant load.
You don't want to regulate the MPPT output to 12V, as it would not be able to float charge your batteries at that level. It is generally safe to float charge (constant voltage) a 12V monoblock at 13.5V indefinitely. Specs on your specific battery should identify the ideal float charge voltage as as function of its specific gravity.
If your batteries turn out to be failing, make sure that you're using deep-discharged rated batteries and not batteries intended for engine starting applications. So-called starter batteries are designed for very high instantaneous current, but relatively low discharge depth (you start your car, then they recharge immediately). Your application will likely pull your batteries down to a much higher depth of discharge on a regular basis, so you'll need a battery specifically designed for this use case if you expect a decent working life from the batteries.
EDIT:
Most MPPTs have a relatively low current output at 13.5V - usually less than a couple of amps. The reason that batteries are used in parallel is to allow loads that exceed the capacity of the MPPT. For this to work continuously, the total energy supplied by the MPPT per day/week must exceed the total energy removed from the system per day/week, as the battery just stores/buffers energy; it doesn't create it.
Consider this example (done in amps rather than watts for clarity, even though watts would be more accurate) - Assume an MPPT with a ~1A output is connected to a fully charged battery. Now assume a 10A load is connected to the system. Roughly 1A of that 10A will be supplied by the MPPT and the remaining 9A will be supplied by the battery. The battery's terminal voltage under discharge will define the voltage at the load and the MPPT will adjust its output to match (being a constant power device). This load can't be sustained, as the battery will eventually be depleted. When the load is removed, the MPPT's output will float charge the battery until it is returned to 100% SOC or until a load is re-applied.
Rapid load voltage fluctuations between 12.0 and 13.5 strongly suggest that the MPPT (or the load, if electronic) is being forced into a fold-back self protection mode as a result of a load that exceeds the MPPT output without adequate battery buffering.
This thread may also be helpful.
What is the frequency of the oscillation you observe?
If it is relatively low frequency, then the drop is probably caused just by energizing the TPS61222 output cap and inductor. You could fix that by adding more hysteresis on the comparator. Seems unlikely to me, however, because the super cap is so large.
If it is highish frequency, it could be caused by inductive and resistive drops in the path between the supercap and the input to the TPS61222 (including the internal resistance of the supercap itself, which is likely considerable). Again, adding more hysteresis on the comparator will help fix it. You can also improve the situation by using a bulk input capacitor right next to the inductor to hold the input to the TPS61222 in the face of the relatively large currents you will see at startup - this will work if you take Simon's recommendation and drive the EN pin of the boost converter instead of a load switch. That recommendation is likely a good one anyways, since it saves you a part.
Note that if you are running a load at the output of the boost, you may observe some sort of "oscillation" any time your load power exceeds the input power from the cell. The solar cell will charge up the super cap until the boost turns on, at which point the power drawn from the SC exceeds that going in and the voltage starts to drop. It continues dropping until the TPS61222 turns off / gets disconnected, and then the process starts over.
Best Answer
There are a few boost controllers that run down that low, but in general it's better to have a higher voltage to start with. 0.5V at full tilt is really low, presumably it's designed to be stacked to get a usable voltage.
Here's an example of one of the very low input voltage boost converters. Of course this one doesn't do much current, so it doesn't really fit the bill...