En todo el tiempo que llevo tocando HTML, nunca había tenido la necesidad de insertar saltos de carro en los atributos ALT y TITLE.

Tras probar lo evidente: <br>, \n, he visto que con un retorno de carro físico, la cosa funcionaba. Aunque claro, con algunos problemas en cuanto a validación.

En conclusión, de estas formas no funciona:
<a href="#" title="Linea 1<br>Linea 2">Enlace</a>
<a href="#" title="Linea 1\nLinea 2">Enlace</a>

Y de esta forma, a veces da problemas de validación:
<a href="#" title="Linea 1
Linea 2">Enlace</a>

Finalmente he encontrado la clave. Consiste en insertar el carácter ASCII 13 (Carriage Return -CR-). La cosa quedaría así:
<a href="#" title="Linea 1&#13;Linea 2">Enlace</a>

Que se muestra en pantalla así:
Enlace