The algorithm requires the polynomial to be monic.

Keeping the coefficients at higher precision also does not matter much if the polynomial evaluation is done at lower precision. It's to be expected that you need high precision, since evaluating polynomials in the monomial basis ill-conditioned.

Increasing the precision proportionally to the degree seems like a decent rule of thumb. But you will not get an algorithm that always works without some much more complicated numerical analysis.