The wording of the 13th Amendment, including the "except as a punishment for crime whereof the party shall have been duly convicted" clause explicitly permitting prison labor, was lifted directly from the Northwest Ordinance of 1787, which organized the Old Northwest (1787 America's territory West of the Appalachian Mountains and north of the Ohio river, roughly the same land that now comprises the states of Ohio, Indiana, Illinois, Michigan, and Wisconsin) as a territory and made provisions for its territorial governance and eventual admission to the US as new states coequal with the existing states.

Art. 6. There shall be neither slavery nor involuntary servitude in the said territory, otherwise than in the punishment of crimes whereof the party shall have been duly convicted: Provided, always, That any person escaping into the same, from whom labor or service is lawfully claimed in any one of the original States, such fugitive may be lawfully reclaimed and conveyed to the person claiming his or her labor or service as aforesaid.

The fugitive slave clause from the Northwest Ordinance was stripped out for obvious reasons, but the rest was copied. This language was used in place of the further-reaching language of an earlier draft written by Thaddeus Stevens and Charles Sumner:

All persons are equal before the law, so that no person can hold another as a slave; and the Congress shall have power to make all laws necessary and proper to carry this declaration into effect everywhere in the United States.

Stevens was one of the leaders of the Radical Republican faction in Congress, and Sumner was one of the more prominent Radicals in the Senate (as well as being the Senator who had been severely beaten by South Carolina congressman Preston Brooks in 1856).

There were three-ish parties in Congress at the time (1864-65) when the amendment was being debated. The Republicans held slightly more than a 2/3 majority of the Senate (34 out of 51 total seats) due to the seats belonging to the seceded Confederate states being left vacant, but only 47% (86 seats out of 183) of the House.

In coalition with the Republicans on most issues were the Unionist and Unconditional Unionist parties, which were made up of politicians who pre-war had been Southern Democrats or Constitutional Unionists (a fusion ticket made up of the remnants of the American or "Know Nothing" Party and the "Oppositionist Party" southern splinter faction of the Whig party). Most Unionists in Congress came from Border South slave states that had not seceded (Missouri, Kentucky, Maryland, and Delaware), from the newly-formed splinter state of West Virginia, and from seceded states whose Senators had opted to serve out their terms instead of resigning (at this point, only one Senator from Virginia was left in this category). Together, the Unionist parties held 3 seats in the Senate (6%) and 25 in the House (12.8%).

The remainder were Democrats: 12 Senators (24%) and 72 Congressmen (39%).

Since a Constitutional amendment requires a 2/3 majority of both houses of Congress (plus ratification by 3/4 of the states), the Radical Republicans needed support not just from their more moderate Republican colleagues, but also from most of the Unionists and at least a few Democrats in the House of Representatives. The final votes for passage of the Amendment for the House and the Senate respectively can be found here and here. As you can see, 19 of the 25 Unionists and 14 of the 72 Democrats in the House voted for final passage, along with every Republican, giving just over the required 2/3 majority.

The changes were thought necessary in order to win the House majority: even with the changes, an earlier vote on the amendment in the House failed on a largely party-line vote, and it took six more months of events (including the fall of Atlanta, Sherman's march to the sea, the progress of Grant's Overland Campaign up to the Siege of Petersburg, Lincoln's landslide reelection, and the election of a new Congress (*) with a 70+% Republican majority in both houses) sealing the fate of slavery in the soon-to-be-former Confederacy for enough non-Republicans to reconsider their opposition to the proposed amendment.

(*) Elections, then as now, are held in November, but the new Congress didn't take office until the following March (later changed to January). The House passed the 13th Amendment in January 1865, during the "Lame Duck" session of the outgoing 38th Congress.

Also playing a role was the amendment being routed through the Senate Judiciary Committee, chaired by Lyman Trumbull, a leading Moderate Republican.

The specific objections to the Stevens/Sumner language mainly focused on the opening clause that "All persons are equal before the law". Substantively-similar language would later be included in the 14th and 15th Amendments by the 39th Congress, but it went too far for the persuadable Democratic congressmen whose support was needed to pass the amendment through the 38th Congress, and was probably a little too far for comfort even for Moderate Republicans and anti-slavery Unionists.

The Northwest Ordinance language was probably selected based on it being more narrowly tailored to the goal of abolishing slavery and on the prior usage providing a clear body of precedent for what the language would mean in practice. The "except as a punishment for crime" clause in particular was probably included not just because it was in the NW Ordinance, but also because prison labor (in a very different form from the Jim Crow era's infamous use of convict labor to approximate slavery) was already in widespread use in the North, particularly in the "Auburn System" of prison management which (among other things) prescribed requiring prisoners to work as a key part of their punishment and rehabilitation.