If you now connect the capacitor to a battery then the voltage $V$ is constant because the voltage is always just equal to the battery voltage. So now we have $Q = CV$, for constant $V$, and when you insert the dielectric it increases $C$ so $Q$ increases by the same factor of $\epsilon_r$.
It is true that the charge increases, but a dielectric is polarised in an electric field and the polarisation of the dielectric reduces the effective charge on the plates of the capacitor.
I can attempt to draw a diagram to show this if it will help ...
Now suppose we put a dielectric slab in between the plates. The field pulls electrons in the dielectric upwards, so the slab ends up with a negatvie charge on the upper surface and a positive charge on the lower surface.
So suppose you're in the middle of the slab. It now looks to you as if the top plate has a charge $Q-q$ and the bottom plate has a charge $-(Q-q)$. So it looks to you as if the charge on the capacitor has decreased.
Since the charge has decreased that means the potential has decreased and therefore the electric field has decreased.
Problem Solving Strategies
Problem Solving Strategies