We probably shouldn't use the word 'melting', but instead 'softening'. I don't think the idea was to take an odd shaped stone, coat it with melting paste, stick it in place and watch liquefied rock ooze out. The whole rock doesn't soften, just a thin outer layer. They likely used the paste on a couple sides of the stone before it was ever fitted into the wall. Let it soften a bit and get it shaped kind of close enough with hand tools. Then add more paste to the lower level and one side of the new rock like you'd do with mortar. As the edges softened up the rock would settle into it's final position simply due to gravity and the weight of the stone. As they said in the video, that's why heavier stones left bigger imprints on the row they sat on. I would also assume the thicker the layer of paste, the deeper it would soften the stone being worked on making it easier to remove bulges, etc.
You would still have the sharp clean edges, especially after they removed the squished out paste/mortar lines later like the video mentioned. That's why there's no visible residue of the paste. They also showed small rock 'plugs' that were softened and installed where there might have been gaps during the whole process. They improved the appearance of the wall by cleaning the joints after the paste did it's job. That's pretty much how they do mortar work today, minus the 'softening'.
They could have back filled as they went to hold it in place while it settled in, which explains why a lot of times the backs looked bad but not the fronts. If they were in a resource rich place, they could make more paste to work on all the surfaces for a nicer (and probably easier to build) wall.
There is one issue that could cause problems. They wouldn't be able to stop work in the *middle* of a layer with a perfect 90 degree angle because there would be no way to get 'molding' pressure from the next stone the following day. So whatever rock they stopped on would have to be at a slight angle like this: / or \ depending on the direction you're adding the next stone. That way the next stone would be applying pressure sideways to mold it into place. And if you look at the walls, you can see those angles all over the place to keep that pressure.