Magento-1.9 – How to Set Font Awesome Icon in Magento Top Links

In any case do not edit the template file (links.phtml). This serves as a general template for all link lists. For example it is used for the links in the footer also.
With toplinks.php you can do whatever you want because is deprecated since CE v1.4.0.1.
I recommend using the xml files that add the links to the top container to achieve what you need.
The addLink method that is called when adding a new link supports some parameters that allow you to add classes and other attributes on li and a tags in the links and some text before the link and after the link.

public function addLink($label, $url='', $title='', $prepare=false, $urlParams=array(),
        $position=null, $liParams=null, $aParams=null, $beforeText='', $afterText='')
    { ... }

If you want to add an icon to my account menu you can set the $beforeText to <span class="icon"></span> and add some styles on the icon class.
For the cart and checkout links it's a little trickier because they are added via a block object not directly from the layout file.
If you need something different for the cart or checkout lins all you have to do is override the methods Mage_Checkout_Block_Links::addCartLink() or Mage_Checkout_Block_Links::addCheckoutLink(). These 2 call the same addLink() and you can pass different parameters to it.

You can also remove some of the top links in your local.xml by referencing them and removing them by name.

<reference name="top.links">
   <remove name="wishlist_link"/>
   <remove name="checkout_cart_link"/>
</reference>

This only work if the top link was created with a name like this:

<reference name="top.links">
   <block type="wishlist/links" name="wishlist_link" />
   <action method="addLinkBlock"><blockName>wishlist_link</blockName></action>
</reference>

For the log in and log out, since they aren't called with a "name", you can't remove it this way.