SQL Server Stored procedures run very slowly after a while
What you're describing sounds like parameter sniffing to me. Parameter sniffing occurs because SQL Server caches the execution plan of the procedure if the plan is not found in the cache. Subsequent executions will use that version of the plan. In most cases, that's desirable since it eliminates compilation time. However, if the characteristics of the data accessed by the procedure's queries varies significantly when different parameters are passed, the result can be very poor performance. 

Your description of the runtimes of short date ranges versus long ranges fits that pattern perfectly. I would guess that the query optimizer is choosing different indexes in the two scenarios.

You're on the right track for your solutions. WITH RECOMPILE can resolve the parameter sniffing in some cases, but recompilation is a high cost to pay on every execution. OPTION(RECOMPILE) on individual queries can definitely help and is sometimes the best answer, but again, it comes at a high cost. OPTION(OPTIMIZE FOR UNKNOWN) is another possibility, but it resolves the issue by providing a plan that's consistent (but may still be horribly inefficient).

Start by reviewing these articles, which explain parameter sniffing far better than I can in a short answer:


Kimberly Tripp, Building High Performance Stored Procedures
Kendra Little, Optimize for… Mediocre?


Then, check the execution plans for your procedure, looking for the specific queries that vary the most between executions. Try OPTION(RECOMPILE), OPTION(OPTIMIZE FOR UNKNOWN), or Kimberly's sp_executesql method on those, rather than the entire procedure.