Voltage drop on lithium batteries
Why do you think you're triggering the boost converter's UVLO?  You almost certainly aren't.
Any Lithium Ion battery of the sizes you are using will not show much voltage drop under such a relatively light load, and certainly not enough to fall below the MT3608's UVLO which is 1.98V.  Even if they are discharged to 3.5V.  A 10Ah cell most definitely would not fall enough under such a load.
If you were really dropping the terminal voltage of your battery that low, you would have triggered the cell's output protection circuitry and it would have permanently disconnected the output of the cell, as discharging a LiIon below 2V essentially destroys by rendering it dangerous to recharge.
The real culprit is probably one of two possibilities.  The first is the over current protection circuitry of the boost converter kicking in.
If the fan draws 1A at startup (not unreasonable for a 0.55A fan), however brief, this will totally overload the MT3608.
Using a conservative 20% ripple current figure (it is probably more), this yields a peak current above what will trigger the MT3608's current limit (4A - though the datasheet implies this limit might vary depending on the input voltage and duty cycle).  This is without even factoring in the diode drop or other efficiency losses:
\$ 12V*1A = 12W \$
\$ \frac{12W}{3.5V} = 3.43A \$
\$ 3.43A * 1.2 = 4.1A \$
But, and I think this is much more likely:
You're using something like a power bank or some no-name mystery cell with a really low current (inexpensive) protection circuit.  The battery can supply more than enough current for your application and should never fall below 2V even if it is at 3.5V at a worst-case load of 4A.  But you're going to be at the mercy of the battery's protection circuit, not the battery itself.  This would cause the output of the battery to disconnect entirely as soon as the programmed current cutoff is reached.
Whatever it is you bought, even if it looks like a bare cell, almost certainly has a protection circuit hidden in it somewhere.  And if it really is a bare cell - you shouldn't be using a lithium ion battery like that, it is dangerous to do so.
Regardless, a single 3Ah lithium ion cell that isn't completely worn out or bad would not fall to the voltage you're suggesting when discharged to 3.5V.  And neither would any other larger capacities.  Adding another cell in parallel would halve the current draw from each cell and also halve the voltage drop due to internal resistance, but considering that this couldn't actually be the cause of the issue, it is hard to say that an extra cell in parallel will solve your problem or not.  It would probably still solve it in the case of an anemic protection circuit, as long as the halved current was within the rating of the protection circuit.
A good way to check this is to just charge the 10Ah cell by slowly bumping up the current until you hit 10A.  You'd need a suitable bench power supply of course.  But what you'll likely find is the battery will suddenly stop charging as if it lost the connection to the power supply entirely once you hit a certain current thats probably around 4A or so.  That lets you know you're hitting some arbitrary current limit built into the battery's protection circuitry.
In the mean time, a much easier solution might be to simply not run the fan at 12V.  Those style of brushless CPU fans will happily run from a very wide range of voltages, with lower voltages resulting in a small reduction in the fan's RPM.  But it isn't going to be a huge difference if you run a 12V at, say, 11V or even 9V.  This would reduce the burden on the boost converter and battery even during startup and would cause only a small reduction in airflow.  You know that you're not going to find a solution easier than just turning a trim pot a little bit, so might as well give it a try.