Function to delete oldest items out of HTML5 localStorage. Can I make it more efficient?
Object.size

First off, if it's ok with you to use ES5 APIs (you use localStorage, it should be okay), then here's a quicker way to get the number of keys in an object using Object.keys.

return Object.keys(obj).length


Delete by N

Also, from what I understand in your code, you're deleting keys by 3's. If so, then you should not hardcode the 3. Instead, have it configurable in your object.

Verbose Variable Naming

Here's one I get often. Name variables according to use. tmpExp will not help anyone understand its purpose. Name them verbosely. I should understand code like I read the back of a milk box or something.

Compress the algorithm

I suggest you compress the algorithm, make it simple. 

Nested loops are just bad for performance. Also, getItem is a synchronous operation, which means that if it freezes, it freezes the UI as well. Nesting that along with a JSON.parse makes it even more slow.

If you can, do operations with the least loop runs and function calls as much as possible. If you can cram several loops into one big loop (like batched operations), then do so.

Here's a proposed fix for makeRoom. Keeping it simple, it just removes the oldest among the stored data.

// Just grab the expiry and store the expiry-key into an object
var expiries = Object.keys(localStorage).reduce(function(collection,key){
  var currentExpirationTime = JSON.parse(localStorage.getItem(key)).expirationTime;
  collection[currentExpirationTime] = key;
  return collection;
},{});

// Get the expiry dates into an array
var expiryDates = Object.keys(expiries);

// For N times, find the oldest (smallest timestamp) and destroy
for(var i = 0; i &lt; N; i++){
  var oldestDate = Math.min.apply(null,expiryDates);
  this.destroyItem(expiries[oldestDate]);
}


getTime now()!

Instead of new Date().getTime(), there's the new Date.now(). Same effect, but saves you memory from creating a new Date instance just to get the current timestamp.