Surely, if ever there was an expression that sounds American, this is it. However, the two earliest examples I know of of rootin’ tootin’ in print date from 1874, and one is from the USA and one from England.
The English example of rootin’ tootin’ is in the English poet Edwin Waugh’s collection of rustic dialect stories, The Chimney Corner, 1874:
“Well… Afore hoo’d bin here three days hoo’d hauve a dozen colliers whewtin’ an’ tootin’ after her every neet.”
[Before she’d been here three days she’d have a dozen miners whistling and hooting after her every night.]
The US example comes from the Indiana newspaper The Evansville Journal, November 1874:
I’m a rooting, tooting, cutting, shooting, carving, card-playing catamount, all the way from Arkansas.
Whether those two above citations are of the same expression or whether they were derived separately in two places I can’t be sure. They do seem to have the same meaning though, so there’s every reason to assume they are one and the same. If that is so then it’s likely that the UK version travelled to the USA – many rural English migrated to the USA in the 19th century but hardly any came the other way.
The phrase itself may well be older than 1874. The English citation above is from a story which uses the colloquial language of rural England, and this would have been in use for many years before it was written down.
Likewise the US example is in a “rootin’ tootin’ cuttin’ shootin’ from Arkansas” format that must have been well used in Arkansas by the time it was recorded. It appears in print frequently enough to make one think it was a popular saying in Arkansas at the time. I would doubt that the journalist who printed it in 1874 was the first to use it.
I suggest that odds are that the term was English first and migrated to the USA, but that’s yet the be proven beyond doubt.