Adding tracks might be possible but given the size of the map its not likely to be of much use. I'd assume that it would work by the same method that grass trampling works on, each time a trample event occurs the ground is also marked with some additional information such as a direction and creature type and some kind of 'group ID' that tells us that the tracks are associated (this way we can pause and give "Tracks found" message when a track is revealed to the player and then skip the message for all the remaining tracks with that group ID avoiding the equivalent of Microcline spamming with every newly discovered footprint)
I do not think that invaders currently cause trampling, at least not when invisible, if they did you would be able to see a line of trampled grass moving across the ground which would be very silly. So if this was implemented the grass tramples themselves would need to remain invisible until detected by a scout. Only a Dwarf who is actively 'scouting' generates the checks necessary to reveal these tracks and their would probably be a check against their skill level to see if they succeed.
The trick to making all of this computationally efficient is to have a small number of things generating the 'pings' of detection. This could be either the scouts OR the invisibles. A combination of techniques might be the better solution. First start with the Invisibles as they are usually going to be in a group use the maps block structure which could have an "invisibles in this block" flag, even the largest war bands would rarely cover more then 4 of these blocks. Then have the detector skill be equally course grained with it applying a "Detector viewing this block" flag again a very powerful detector can would cover only a few such blocks, these course grained flags are extremely easy to update every single cycle, just wipe the previous flag and mark the flag true while iteration over creatures, each time one of the flags is raised check to see if both are true, if so a more fine-grained tile-by-tile check is needed but because this fine-grained check is happening only at the final moment when actual detection is possible it will be SOOOO infrequent that its cost can practically be ignored.