The LM317 generally has excellent load regulation, which means very little variation in output voltage when the load current changes. There is obviously something wrong with your circuit.
Start by measuring the voltage at the input of the (second, voltage-controlling) LM317. What is it, with no load and with load? With 12 V out, it must be at least 15 V or so.
Measure the voltage at the input and output of the first (current limiting) LM317. The drop from input to output should be small, roughly 2 V or less (the dropout voltage of the LM317). When the current limit of 500 mA is exceeded, then this voltage drop will suddenly increase ... this is how it limits the current, by reducing the voltage at the load.
What kind of output capacitor are you using? I wonder if the LM317 is oscillating. Try a different size capacitor. Try adding a resistor of a few ohms in series with the capacitor. Increasing the ESR like that can improve stability when a regulator tends to oscillate due to the capacitive load. It is also possible that the first LM317 is oscillating, so try the same tricks there. If you have access to an oscilloscope, use it to look at the voltages (use AC coupling) to see if there is oscillation. You will need a 10 MHz or better scope.
You definitely need a minimum load for the LM317, of 10 mA or more. Setting R1 to 120 Ohm satisfies this even when no other load is connected, since the Vref of 1.25 V will appear across this resistor: 1.25/120 ~= 10 mA.