Hello Panjandrum, welcome to UsingEnglish! (I seem to know the face.)
I don't remember hearing "Second of all"; but if I did hear it, I would take it as a humorous formation. Or perhaps a sign of discomfort with the bare "Second", in someone who had been told that "Secondly" was somehow unmanly and weak (as I once was).
I'll be interested to hear what other members have to say.