During a supernova, a star blasts away its outer layers; this actually reduces the mass of the star significantly.
Any star or planet has an escape velocity - the slowest an object must be traveling for it to escape the gravitational field of the star/planet. For Earth, this is 11.2 km/s. (Note that this value doesn't account for any atmospheric effects.) For a black hole, however, the escape velocity at the event horizon (the "edge," in some sense) of the black hole is the speed of light, $c = 300,000 \text{ km/s}$. For anything within the event horizon to escape the pull of a black hole, it must exceed the speed of light, a physical impossibility. There's a certain mass-dependent radius - the Schwarzschild radius - to which an object must shrink in order to become a black hole.
Newton's Law of Universal Gravitation, which you stated, doesn't apply in its standard form to light. Rather, you need to use Einstein's general relativity, which considers gravitational forces in a much different light than Newton did. However, Newton's Law of Gravitation can intuitively apply here: when a star collapses, $m$ does decreases. However, $r$ becomes much smaller, so the net effect of these changes is the creating of a stronger gravitational force on the surface of the remaining object.