I'm curious if anyone can trace the roots of Galula's influence on American COIN doctrine.

I'm sure that having Pacification in Algeria in the files at RAND provided some accessibility (and ease of distribution given that you can download the .pdf and email it), but the first copy of Counterinsurgency Warfare: Theory and Practice that I ever saw was an old copy on a friend's bookshelf which had been issued to his father for a class on revolutionary warfare at USMA back in either 1969 or 1970. Based on that, it seems that Galula had some currency back during the time of Vietnam as well for his book to have found its way into the USMA curriculum.