The short version of this answer is that when an eidolon crosses a life link threshold while returning to his summoner, his maximum hit points increase but his current hit points do not change, even though he lost current hit points when he crossed that threshold while moving away from his summoner. You can even kill an eidolon by bull rushing, pulling, pushing, or repositioning it (or moving it magically) across a threshold repeatedly. To directly answer your question in the comments about healing an eidolon, healing is never more effective while the eidolon is far from its summoner, and could be less effective (if the healing would bring the eidolon over its reduced maximum hit points).
Since damage should be kept track of instead of counted down thats fine.
This is an incorrect assumption, and is what's causing the confusion regarding life link. Nonlethal damage is tracked separately, but normal damage is subtracted from your current hit points. It's ok if you decide to track it as "damage taken" (and quite a bit easier, I often do so for creatures besides eidolons), but sometimes an ability needs to use the actual current hit points for something, like life link does, and it's important not to get confused: "damage taken" isn't a thing the game normally tracks, only current and maximum hit points; which means your "damage taken" marked might have to be altered to fit the new game state. Keeping this in mind, I'll explain an example, telling you how much damage the eidolon should have marked on his sheet if you want to keep tracking his hp that way, but I assure you it's much easier to simply track the eidolon's current hp (subtracting from it when he takes damage and adding to it when he is healed) than to track damage taken if he's going to be crossing life link thresholds.
Starting from an eidolon with 100 maximum hp and 44 current hp (that is, having 56 damage marked on his sheet) and within 100 feet of his summoner:
When the eidolon moves beyond 100 feet from his summoner, his current hp will drop by half to 22, and his maximum hp will drop by half to 50. You should either scribble a 50 near his max hp on his sheet and erase all but 28 of the marked damage (to show he's at 22 of 50 hp), or you should put a circle around 50 of the marked damage (to represent damage that can't be healed, since it's actually max hp loss) and increase his total marked damage to 78, to represent him being at 22 out of 100 hp.
When the eidolon then moves beyond 1,000 feet of his summoner, his current hp will drop by half again (a total loss from normal of 75%) to 11, and his maximum hp will drop by half again to 25. Again, you should either scribble a 25 where the 50 was near his max hp on his sheet and erase all but 14 of his marked damage (to put him at 11 of 25), or you should draw a second circle around another 25 damage marks (making 75 damage marked off as max hp loss) and increase his total marked damage to 89 (so it's clear he's at 11 hp from his normal max of 100).
When the eidolon then returns to within 1,000 feet of his summoner, his current hp will not change and his maximum hp will increase from 25 to 50. You should either erase the 25 and put back the 50 and increase his marked damage to 39 (to show he's at 11 of 50), or else erase the circle around the 25 damage marks and leave his total marked damage at 89.
To answer your side question about healing the eidolon while he's far away from you, the most you could heal him to at this range would be 25 hp. You'd either end up with a scribbled-in 25 max and no damage marked, or else 75 damage marked and circled and no other marks. When he came within 1,000 feet like this, you'd either change his scribbled-in max to 50 and mark 25 damage (to show he's at 25 of 50), or else just erase the circle around the 25 damage and leave him with his total marked damage at 75.
When the eidolon then returns to within 100 feet of his summoner, his current hp will not change and his maximum hp will increase from 50 to his normal max of 100. You should either erase the scribbled-in 50 and increase his marked damage to 89 (so he'll be at 11 of 100), or erase the circle around the the 50 damage marks and leave his total marked damage at 89.
The "healed" eidolon returning to within 100 feet of his summoner would either have his scribbled-in 50 erased and his marked damage increased to 75 (so he'll be at 25 of 100), or else just the circle around the 50 damage erased and his total marked damage left at 75.
Two quick examples of how nonlethal damage interacts with life link, since it is tracked separately (not as a part of current hp). 1: Take the above example eidolon with 44 hp and 100 max hp, but also with 15 points of nonlethal damage. When the eidolon crosses the first threshold, his current hp drops to 22 (and his max to 50), but he still has 15 points of nonlethal damage, meaning he's now much closer to being knocked unconscious than he was. If the eidolon then crosses the second threshold, he'll drop to only 11 hp (and 25 max hp) and 15 nonlethal damage, meaning since he has more nonlethal damage than current hit points, he immediately falls unconscious.
2: Imagine an eidolon with 100 current and maximum hit points (that is, he is unhurt, except...) with 51 nonlethal damage done to him. When he crossed the first threshold, he would drop to 50 current and maximum hit points. Since his nonlethal damage is higher than his maximum hit points, the excess point would convert to normal damage, leaving him with 49 current hit points, 50 maximum hit points, and 50 points of nonlethal damage. He would also fall unconscious. If someone carried him past the second threshold (or if his summoner walked away, beyond 1,000 feet, whichever), he would drop to 24 current and 25 max hit points. The 25 points of nonlethal damage beyond his new maximum would convert to normal damage, bringing him to -1 hit point and banishing him back to his home plane. (It's an individual GM's call as to whether this damage conversion counts as damage the summoner could sacrifice hit points to in order to prevent the eidolon from being banished.)