Muy probablemente se trata de un diminutivo femenino de latín ALTUS, -A, -UM con evolución fonética que implica la vocalización de /l/ en posición anteconsonántica, esto es, ALTA > auta, estadio previo a la posterior monoptongación del diptongo resultante auta > ota. Esta es la evolución fonética regular en castellano, aunque en este caso la palabra fue sustituida en buena medida por la reintroducción del latinismo alto, alta. En el caso de nuestro topónimo cabe la posibilidad de que, por motivos que se nos escapan, la evolución haya quedado detenida en el estadio intermedio auta. Otra posibilidad, muy semejante a la anterior, es considerar que la evolución habría culminado de la manera esperable en ota y que en este caso se habría aglutinado una vocal /a/ procedente del artículo o incluso de sustantivo villa, que a menudo precedería al adjetivo, con posterior cierre de /o/ en /u/ para formar diptongo, esto es, *la otiella > *l'aotiella > l'autilla o bien *villa otilla > *vill'aotilla > *villa autilla > Autilla. Sea como sea,  la documentación más antigua a nuestra disposición es la de la estadística de 1345 que muestra la forma Otiella, lo que parece abogar en favor de la segunda de la posibilidades. El  Becerro de las Behetrías, de pocos años después, muestra ya la forma actual, que se repite desde entonces sin cambios. Como se verá más abajo, en el apartado de cognados, la toponimia de Palencia, muestra también algún caso de la forma masculina Autillo, mientras que en el resto de España no es difícil encontrar casos de Otilla, Otillo y, naturalmente, de Altilla, Altillo. 

En lo que hace al segundo elemento del compuesto, documentado ya desde el siglo XVI, se diría que, a pesar de la preposición y el artículo, no se trata del nombre del árbol, sino del adjetivo derivado de ese nombre del árbol, pino, pina, de significado "empinado", "escarpado", uso ahora en retroceso, pero en tiempos plenamente popular. Sería, pues, algo así como "la villa altilla que se encuentra en terreno empinado, escarpado". Ciertamente hay aquí un uso redundante, pero esto es algo natural y frecuente en toponimia.