<Other opinion> In context like "마음이 가는 대로 해라" , 의존명사 -대로 means '어떤 모양이나 상태와 같이' like you said, so using -대로 would be correct.

However, in this song, "내가 가는 데로" it is kind of an abbreviation of "내가 가는 데로 가자". In this case, 데로 is the union of 의존명사 '데'(which means place) and 조사 '로' (which means direction). So this sentence means we go "where" I go, and this is correct.

So, in my opinion, although your example for -는 대로 is correct, but in this case -데로 is correct. In other words, original lyrics is not wrong.

In addition, i will give you more example. 1. 지금 가는 데가 어디야? Where are we going? 2. 내가 사는 데로 가자. Let's go to my place.