In cat-o'-nine-tails, the cat was a stick and the nine tails referred to the nine lashes that were attached to it:
To show this use of “cat”:
OED at Cat (n)
†10 c. The cat-stick. Obsolete.
1636 Divine Trag. lately Acted 23 Sundry youths playing at Catt on the Lords day, two of them fell out, and the one hitting the other under the eare with his catt, he therwith fell downe for dead.
And to explain "playing at Catt"
Tip-cat
https://www.britannica.com/topic/tip-cat Tip-cat, also called One-a-cat, outdoor game dating back at least to the 17th century and introduced to North America and elsewhere by English colonists. The game was widely popular in 19th-century Great Britain and in early 20th-century North America.
Although there are many varieties of the game, all involve a stick about 3 ft (1 m) long, used as a bat, and a piece of wood (the cat) about 4 in. (10 cm) long, 1 to 2 in. (2.5 to 5 cm) thick, and tapered at the ends.
And thus
cat-o'-nine-tails n.
1. A whip with nine knotted lashes; till 1881 an authorized instrument of punishment in the British navy and army.
1695 W. Congreve Love for Love iii. i. 44 If you shou'd give such Language at Sea, you'd have a Cat o' Nine-tails laid cross your Shoulders.
It is clear from Congreve’s use that he and his readers/audience were familiar with the instrument. We can conclude that the name was used earlier, and indeed we have:
“Not enough room to swing a cat”
Swing (v.)
7. a. transitive. To cause to oscillate, as a body suspended from a support above; to move or sway (something) to and fro in this or a similar manner. to swing a cat (i.e. holding it by the tail); in no room to swing a cat in and similar expressions, said of a confined or narrow space. to swing the lead.
1665 Medela Pestil. 57 They had not space enough (according to the vulgar saying) to swing a Cat in.
I think the OED’s idea of swinging an actual cat to and fro is a little fanciful, and “cat” was, in fact a cat-stick, or any stick and to swing would mean to whirl about or wield a stick.
“Letting the cat out of the bag” There is no reason at all why a cat-o'-nine-tails should be kept in a bag – what would be the reason?
This is more prosaic. I don’t know whether you have ever tried to put a cat into a bag, but it is not an easy job as the cat resists, and once out, it runs off at high speed. Thus the secret figuratively escapes and cannot be brought back.