The problem with sandstone caves is that although they form rather easily, as it is easily eroded by the water. The reason we don't normally see large sand stone caves is how fragile/unstable they often are when compared with limestone, being that sandstone is a much softer rock. We found and explored a few sand stone caves near the North Pennines a few years back and let me tell you those places were definitely not stable. Though one did get over 40m in length and even had quite a large chamber.
So it is quite amazing these systems have formed in such a size and from the photos and the fact you can explore them, appear to be generally of good quality rock. I would therefor guess that these caves in Megalaya are not pure sandstone, and are probably a sandstone/limestone composite, this seems likely due to the proximity of large limestone systems.