I believe the etymology is not simple reduplication but rather an abbreviation of the faux-pidgin proverb "softly softly catchee monkey". (Of course, the faux-pidgin includes reduplication, but this occurs in the postulated pidgin rather than in Standard English.) The full form was popularised by Baden-Powell's The downfall of Prempeh (1896); he called it an Ashanti saying. It predates him:
- Autobiography (1811) of Mary Wells quotes "an itinerant black preacher" with "Softly, softly, brethren, and you'll catch a monkey!".
- Archer Polson (1840) attributes "Softly, softly, catch monkey" to "the negro".
I couldn't antedate the "catchee" form at Google books before Baden-Powell.