Yes, it's completely normal. Electrolytic capacitors (and also typically high capacitance MLCC capacitors) are not usually designed into applications where tight tolerance is important. For a filter capacitor -20/+80% is sometimes just fine.
You should use an MLCC ceramic capacitor, but keep in mind that the tolerance can be worse than 20%, and almost always in the wrong direction- down, when you take voltage coefficient into account. Very small (physically) capacitors operated at close to the rated voltage are usually the worst in that regard.
Ceramic caps are what is recommended in the datasheet. Ceramic capacitors have lower ESR (they are "better") but that may cause problems in some situations, but in this case there are no issues from ESR.
The datasheet says (for a particular configuration):
Use standard value 10 μF, 25 V, X5R, ±20% ceramic capacitor (that is, Panasonic 1206 ECJ-3YB1E106M
If you were to subsitute a Murata 0402 10uF/6.3V cap (adequate for a single 4.2V cell) the tolerance is given as +/-20% but typically at 4.2V the capacitance would be less than 3uF, and probably less than 2uF if you take temperature and bias and tolerance into account. So +/-20% is a bit of a dream. Maybe at room temperature and with 0V across it, plus they can actually make the capacitors much more accurately than +/-20% under set conditions so they're actually cutting it on the low side (typically 9uF at room temperature with 0V bias).