I learned from one of my guitar teachers that the "shave and a haircut" phrase originated with the first 78 rpm records, which only held two minutes of music on a side. I don't recall the exact amount of time it takes to sing/play the phrase, but when that number of seconds was left on the record side, the band would stop whatever they were playing and add the tag onto it. I don't know where my guitar teacher learned about this, but it sounds plausible to me.