This is easy to replicate by simple adding Suzanne to the scene, enabling Soft Body and enabling Self Collision - and the issue seems to be specific to Suzanne (the other primitives don't exhibit the problem). You can tell something is very wrong by checking the Dimension of the mesh (in the Properties panel (N)) on the second frame - it jumps immediately to some very high values :
The problem appears to be due to the geometry of the mesh - specifically Suzanne's eyes. The eyes are not connected to the rest of the mesh and actually overlap. This is resulting in particularly odd results with the self-collision - presumably as the overlapping vertices repel each other with almost infinite force.
To avoid the problem, in Edit mode (Tab) click a vertex on one of the eyes, hold Control and press Numpad + a few times until the whole eye is selected. Move the eye away from the head. Repeat for the other eye - so that both eyes are no longer overlapping the head.
Now run the simulation and it should behave normally.
I got some interesting results by just moving the eyes a little way away from their original locations. This, presumably reduced the repulsion forces to much smaller values, while still being too close for a stable simulation, resulting in Suzanne being pulled apart rather than being completely obliterated (I think the eyes are being repelled backwards at high speed through her head while the head is being launched forwards) :
So, in summary, the problem is due to overlapping geometry/vertices. Fix the geometry to avoid such problems.