Why are black holes that massive? Today known most massive star, R136a1  weighs approximately 256 times the mass of our sun, how did supermassive black holes, with a mass of 10 billion times the sun form?

I understand, that when a star becomes black hole, its density increases, but does its mass also grow?
The mass of a object does not increase when it collapses into a black hole. So a supermassive black hole must have started off quite small, and then grown.

The formation and growth of supermassive black hole is not settled science. Supermassive black holes probably started as large stellar mass black holes (The very earliest stars could have been very large, and were almost entirely free of any heavier elements, and could have collapsed to form black holes with a mass of about 100 suns) The black holes then grew as more matter fell into them. 

There is a strong correlation between the size of a SMBH and its galaxy. Its not clear why this is, but it suggests that the environment that drove galaxy growth, also contributed to the growth of the black hole. 

This article on the Growth of supermassive black holes across cosmic time may interest you.