That said, I just don't get a sense of how. How this could be the same man that slaughtered prisoners, crucified NCR soldiers, ordered women [censored] and ordered children shot down? I mean getting set on fire would change your outlook on life but seriously, there's no credible reason for how he could have justified his actions and then done a 180* turnaround.
It's not as simple as being "set on fire". After suffering a terrible failure, he was humiliated by his superior and the people he commanded. He was cast out and left for dead. His entire reason for living was gone. When your entire way of life is completely destroyed, it has a profound impact on how you view yourself and your place in the world. Because all momentum is lost, the experience causes you to evaluate and re-evaluate how you have reached this point -- and how to move forward.
There are thousands, if not millions, of examples of soldiers in history who engaged in ruthless -- often cruel -- behavior in times of war only to either return to an "ordinary" civilized life later. Some of them have no problem with what they did, others repress their memories as much as they can, and still others suffer strong crises of conscience that force profound changes in them. As Graham describes, his path to becoming the Malpais Legate was made up of many small compromises that turned increasingly sinister and brutal. At first he thought he was making the best of a bad situation and doing what needed to be done, but in the end he and Caesar had built a society on a foundation of fear and brutality. Caesar had a more grand vision for where the Legion was going, but Joshua Graham was caught up in the day to day maintenance of a tribal army engaged in bleak and often monstrous behavior. It was not until he was removed from that environment that he was able to reflect on his past. He could have chosen to blame Caesar, but in the end he blamed himself. The only people he knew in the world who could possibly accept him were the New Canaanites, so that's where he headed.