Maul makes his first appearance in Star Wars: Rebels in the episode "Twilight of the Apprentice," which takes place in 3BBY, meaning it takes place three years before A New Hope. At that point, Maul had lost any galactic importance and lived a lonely, hermetic life. Since Maul is still in control of a powerful criminal organization in Solo, we can assume the film takes place before that point.
Maul's latest canonical appearance prior to the rise of the Empire, which we see plenty of evidence of in Solo, is in the prologue of the novel Ashoka, which takes place concurrently with Revenge of the Sith, in 19BBY. At this point, Maul still has criminal connections, meaning Solo takes place sometime between 19 and three years before A New Hope, given the possibility of a near-imediate Imperial transition on Corescant.
Since Han is in the military for three years, we can further narrow that down to between 16BBY and 3BBY for the main plot of the film.