Creo que la expresión proviene de la forma en que se puede echar a un perro de un sitio, asiéndolo por la piel del cuello y por el lomo junto a la base del rabo y lanzándolo afuera, de forma que caiga sobre sus patas. Igualmente se da la imagen de asir a alguien de la misma forma usando su indumentaria, y lanzándolo para que caiga en la calle a cuatro patas, como los animales.
Expresión harto antigua, se encuentra en textos de hasta el siglo XVII y posiblemente sea bastante anterior:
Llevaron cuanto en toda la casa hallaron, que no faltó sino llevarnos a vueltas dello a mí y a mi mujer; empero ¡tanto monta!, pues dieron con las personas de patitas en la calle.
Mateo Alemán, "Segunda parte de la vida de Guzmán de Alfarache. Atalaya de la vida humana", 1604 (España).
Y mereçe que le pongan de paticas en la calle.
Francisco de Quevedo y Villegas, "Entremés de Bárbara", a 1620 (España).
A pesar de su antigüedad, la expresión no fue recogida por el DLE hasta 1899. Aunque encontramos su definición en el Vocabulario de refranes y frases proverbiales de Gonzalo Correas, de 1627:
De patitas en la kalle.
Entiende: poner, a persona ke lo mereze; despedir, echar de kasa.
[...]
Poner de patitas en la kalle.
Sinifika: poner en la kalle a un mozo o moza despedidos porke no hazen lo ke deven en kasa.