I'll start of with a section about naming and understanding of the concepts involved.
Side-Effect-Free Functions is a name that will mean different things to different people. The explanation in common English is "a function without unintentional consequences". If you use Side effects as explained in software science (wikipedia), a side-effect means any state change in the system. The explanation will then change to "a function without state changes". Eric Evans in his Domain Driven Design (DDD) book further narrows the side-effect concept to mean "any change in the state of the system that will affect future operations". So we have a situation where we have a common expression which is supposed to be understandable, but you need to be aware that that people can think of three different things when you talk about this.
Another concept we need to define is Functions. Functions is another concept with different meanings in different settings. In some languages, functions and methods means different things, which means you'll have two separate concepts. In .NET you only have methods, but in my experience functions and methods are used as synonyms in .NET realm. In DDD functions are explained as being operations that return results with no observable side effects. In DDD it is further explained that methods that result in modifications to observable state are called commands. I think that's a definition that is lost on most developers. I think it is more important to focus on the concept rather than that, so I won't pay more attention to that.
(Just a stupid observation: If Functions as defined in DDD means "operations that return results with no observable side effects", then coining an expression called "Side-Effect-Free Functions" does in fact not make any sense, since you can't have side effects in DDD Functions.)
There is a reason why we would want to separate operations that will change state and operations that only queries for information. Queries for information is in essence safe to use at any given moment, whereas state-changing operations, even if perceived safe, can be very hard to be certain about in a complex system. By separating them completely, you'll have an easier job handling that complexity.
I'm not so sure that this should be applied in every situation. But what I believe is an absolute demand is that you should be able to trust that a given method/function/operation does exactly what it says it does. Trust is the big thing here. If you have a method called GetBills(), and you in fact do a call to a GenerateBills() method within, we have a big trust issue! Let's not focus on the fact that these don't belong together, but you should at least have followed the concepts behind Intention-Revealing Interfaces, and named it as GenerateAndGetBills() or such.
I believe the biggest issue here is the same as I came into in Intention-Revealing Interfaces; If you can't be sure that the parts of the system you are working with are behaving the way you think they should, then you'll use all your focus making sure they do, and not on the problem at hand.
DDD also has a conclusion worth reading: "Place as much of the logic of the program as possible into functions, operations that return results with no observable side effect. Strictly segregate commands into very simple operations that do not return domain information."
Have a look at the link provided in Morten's comment below for more info on commands and queries. Thanks :)