As verbs, both imply careful following or reconstruction in order to find or identify a path. The difference is in direction & point in time:
Verbs
To trace: follow the completed path backwards from its current point to where it began.
To track: follow the emerging path forwards from your starting point to wherever the thing currently is.
When you "trace" a cellphone call, you try to determine its origin. This is the same whether done right now, or for a call made a month ago. You go backward to the starting point.
When you "track" a cellphone, you monitor its current location, right now, and follow it wherever it goes in the future.
Nouns
You can also use "track" or "trace" as a noun, both of which basically mean the same thing: a sign that something was there. A "trace" may be less obvious - a small/tiny amount or just a hint. A track is more obvious, well-worn by repeated use.