There's a couple of advantages the MER batteries have vs typical LiIon batteries here on Earth:
1. No high-temp storage or operation. How often is a laptop/phone left in a car or trunk in the heat? And turned on without waiting for the battery to cool down? Low operating temps extend battery life and prevent self-discharge.
2. Relatively low drain vs their capacities. While fairly large batteries, their drain doesn't look that large vs their capacity. During the highest drain activities in the daytime , the solar panel provides additional current. During nighttime the primary activity might be radio comms without movement. Laptop and cellphone batteries have frequent high-drain activities while disconnected from their charging system, ie watching a video over the air.
3. Relatively slow charging cycles vs their capacities. People need fast charging for their batteries, so consumer charging circuits typically charge at max rates - 1C/Ah typically vs what looks like .2C/Ah peak for the rovers.
4. Low-vibration environments. Well, other than launch and EDL, the vibration environment is pretty benign on Mars. Having to design for launch/EDL levels of vibration might also have endurance side effects - better connections, etc. Phones/laptops are often dropped or jarred on tables, etc. Probably a minor effect.
5. Individual cells are balance-charged. Lithium chemistries really, really hate being overcharged. What typically kills cheap laptop batteries is a design that uses a single charging circuit, passing through all the cells. These cheap designs cutoff charging once all the cells have reached nominal. If a cell reaches nominal early, it gets overcharged while waiting for the slowpokes, hurting its capacity and making it hit nominal even earlier the next charge cycle. Typically when new all the cells are more-or-less matched, but over time they drift apart. This is more important for LiPoly chemistries than LiIon, but it still matters for battery lifetime over a few hundred charges. People can tear apart used laptop batteries to get the "good" remaining cells for other uses.
6. Not charging to full rating. Continuously charging a Lithium battery to its full rating will also hurt lifetime. Newer laptops can be setup to only charge to 50-80% during the week and 100% on the weekends, or on-demand. Looks like other than EDL, the MER batteries kept below ~75% capacity. Old laptops used to keep their cells at 100% all the time while plugged in for extended amounts of time, seriously compromising their performance. Smarter chargers now charge to the requested level, and shutoff until the level has dropped an amount, typically 3-5%. They also can be setup so that the system load is not run directly off the batteries, allowing the charger to provide power directly to the system without routing it through the battery first. Also, the MER charging is always done in a pretty benign environment, with batteries that are presumably pretty cool.
7. No intentional deep-discharges. This, IMO, is the biggie. Looking at the graph in the paper, the only time MER batteries were ever deep discharged was the Spirit anomaly, otherwise they are kept at about 50% DoD. The anomaly drained her batteries to the cutoff voltage (Lithium chemistries are damaged when drained completely, unlike NiCd or NiMH. Batteries typically have a self-protection circuit that cuts the ground line below a minimum voltage during discharge.) People often drain laptops and phones until the battery is "dead" with the internal cutoff circuit activated - what's worse, they often turn the phone "back on" - with the phone off the battery rises slightly above cutoff, and during boot the power consumption is much lower so the battery continues to drain until the radios are activated and then the phone dies again. These deep discharges really hurt battery lifetime.
I don't know how accurate the capacity measurements are for the MER batteries, typically a gas-gauge chip is placed in series with the battery and reports capacity basically by comparing current IN versus current OUT. Over time they need to reset their count by doing a "training cycle" - to relearn the battery capacity. Without these training cycles the reported numbers get more and more inaccurate - if you have ever had a device that went from 30% charge down to "OMG I'm gonna die" it's because its gas gauge needed to be retrained. The reported % number is based on a certain capacity, if your battery has degraded below that capacity number, as it drains the battery self-protection circuit flags a warning before it cuts off the battery, hence the OMG message. Typically there is a maximum amount the capacity can go down during each training cycle, so it might take more than one to become accurate again. Since there are two packs per MER, it's possible one battery pack could do a training cycle while the other is in use, but it doesn't seem like that's reflected in the graphs. Maybe they are estimating capacity based on the cell voltage, which is pretty inaccurate (hence the invention of the gas gauge chips). It does look like newer gas gauge chips model aging internally, not sure what was space-rated 15 years ago during MER development though.
http://www.ti.com/product/bq27741-g1 is a sample gas gauge chip.
I've done some embedded HW/SW development for cellphones and mobile devices using LiIon and LiPoly batteries, but I am not a battery engineer.