What may have felt like instability would just have been the props becoming slightly out of balance due to the ice. They are big props and any out of balance effect is quite large.
Increasing the propeller RPM, not engine, helps to shed the ice. Lucky you weren't sitting next to the props or you may have felt and heard large chunks of ice smacking against the side of the fuselage as they came off.
With deice boots on such turbo props it's necessary to allow some ice to build up before they are activated. So you will see ice building up on the leading edges before it's got rid of.
There are procedures to follow when encountering severe icing and also approach and landing with ice on the aircraft.
How serious was it? Well it appears to have been dealt with properly so not serious at all. IF the situation was allowed to develop further then it may have become a bit more serious...but it wasn't so that's ok!