In case you find it useful here is a simple computer enumeration for $\ell,r\le 20$ $$ \begin{array}{ c|r|r*{19}{r}} \ell\backslash r& \sum & 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\ \hline 1& 1& 1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 2& 1& 0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 3& 3& 1&1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 4& 4& 0&1&2&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 5& 12& 1&3&5&2&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 6& 22& 0&3&7&8&3&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 7& 61& 1&7&20&18&11&3&1&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 8& 122& 0&4&24&41&33&15&4&1&0&0&0&0&0&0&0&0&0&0&0&0\\ 9& 355& 1&15&69&106&93&47&19&4&1&0&0&0&0&0&0&0&0&0&0&0\\ 10& 765& 0&10&74&192&227&161&71&24&5&1&0&0&0&0&0&0&0&0&0&0\\ 11& 2243& 1&31&221&516&632&464&249&94&29&5&1&0&0&0&0&0&0&0&0&0\\ 12& 5020& 0&16&222&800&1334&1288&815&374&129&35&6&1&0&0&0&0&0&0&0&0\\ 13& 14951& 1&63&677&2260&3732&3665&2522&1290&530&163&41&6&1&0&0&0&0&0&0&0\\ 14& 34599& 0&36&655&3242&7080&8902&7325&4364&1992&736&211&48&7&1&0&0&0&0&0&0\\ 15& 103641& 1&127&2019&9282&20087&25322&21704&13836&7053&2903&986&258&55&7&1&0&0&0&0&0\\ 16& 246070& 0&64&1902&12578&35447&55860&57304&42202&23895&10967&4157&1301&321&63&8&1&0&0&0&0\\ 17& 741510& 1&255&5923&36592&101567&160201&167476&128416&77918&38912&16377&5734&1675&383&71&8&1&0&0&0\\ 18& 1800739& 0&136&5513&48097&170563&330313&409966&362207&244779&133712&61152&23814&7803&2131&463&80&9&1&0&0\\ 19& 5451731& 1&511&17206&140476&492009&953828&1197472&1083274&764487&443648&218859&92624&33690&10342&2663&542&89&9&1&0\\ 20& 13499887& 0&256&15879&180845&799195&1873028&2765328&2869554&2260169&1430391&758236&345860&136814&46726&13559&3296&641&99&10&1\\ \end{array} $$
I used the following basic recursive program in Pari/GP and let it run for 4 minutes :
lessOrEqualReverse(P,r) = { \\ Is the promenade P lexicographically less than or equal to its reverse?
local(B, x, y, z); B = Vec(0, r); z = 0;
forstep(i = #P, 1, -1,
y = B[x = P[i]];
if(y==0, B[x] = y = z = z+1);
if(y < P[#P+1-i], return(-1)); \\ Return No as an answer
if(y > P[#P+1-i], return(1)) \\ return Yes (less than) as an answer
);
return(0) \\ return Yes (equal) as an answer
}
enumeratePromenades(P, A) = { \\ P is a promenade to extend, A hold a list of neighbours for every node in P
local(z, Az); z = P[#P]; \\ z is the current last node in P
if(z>1 && lessOrEqualReverse(P,#A)>=0, C[#P-1,#A-1]++); \\ Count the current promenade if it doesn't end with the starting node 1 and is preferred to its reverse
if(#P>N, return); \\ Don't go any deeper if max length has been reached
Az = A[z]; \\ Current neighbour list of last node
for(i = 1, #Az,
enumeratePromenades(concat(P, Az[i]), A) \\ Extend P with every known neighbour of its last node
);
A[z] = concat(Az, #A+1); \\ Temporarily add a newborn node to z's neighbour
enumeratePromenades(concat(P, #A+1), concat(A, [[z]])) \\ Extend P with the newborn node
}
N = 20; C = matrix(N,N);
enumeratePromenades([1],[[]])
C
The idea is to label the start point with 0, the next point on the promenade with 1, then the next with 0 or 2 according to whether the promenade goes back or reach a new third point, and so on. Then it's only a matter of counting corresponding finite sequences of integers.
This seems to be highly related to https://oeis.org/A186952 because when -- unlike what you want -- you distinguish the start point from the endpoint and further allow both to be the same, you get the sequence
$\sum_r = 1, 1, 2, 4, 9, 20, 48, 113, 282, 689, 1767, 4435, 11616, 29775, 79352, 206960, 559906, 1482188, 4064235, 10901289, 30265366$
for $0 \le \ell \le 20$, which is the mentioned oeis sequence.