Add new shard - always best? In our setup, we currently have 3 shard set sharded cluster, each shard being a replica set of 3. Our writes are about to go up significantly to implement a new feature, and we know the extra data will be necessary. The nature of our writes are basically all upserts(which will likely be updates) and updates where we increment a particular field by 1.

Our updates are always being incremented by 1 and the way our data is distributed, not all documents are treated equally, some get their fields incremented a lot more. An alternative solution that I thought could be effective is to have some type of middle man, like a few Redis databases (or some smaller mongods) where we do the updates to them first and after about 5 minutes (or use some queueing system), we have a bunch of workers consume the data and update the actual live cluster with the documents. This would save our main cluster a ton of writes as it would allow certain update heavy documents to accumulate their updates and could save us a ton of writes (exact numbers I will post shortly in an edit).

So bottom line, when is adding another shard not the right solution?
Nothing here immediately looks like a Sharding issue. Sharding will have a more significant impact on your Reads than your Writes. There are other areas, for Write performance, I would explore prior to spinning up more resources. There is also a larger topic of how your collection is sharded. You could easily, as per your description, have some documents be updated more than others. You could easily have hotspots in an improperly sharded cluster thus sharding will provide you little performance benefit. 

MongoDB has changed since your question was posted. Circa 2014; you can now better leverage bulk operations. In other words, one request could carry more operations. That itself may already resolve the presumed issues you are referring to and eliminate the need for a middleman. If it does not, then yes you could use your proposed middleman approach. I work on a project that utilizes such a solution to pump much more data into a 3 shard development environment with an eye towards 17 shards. That is mainly due to C# driver inefficiencies.

Prior to a new shard, I would first explore setting your read preference to SecondaryPreferred. This will allow your primary node in each RS to leverage more resources for Write operations. 

One could also argue you should reexamine how your documents are modeled. You may benefit from consolidating some documents if the Read operations tend to query a lot of pseudo-related data across many documents.