Lasso on sklearn does not converge

Try increasing tol.

From the documentation:

tol : float, optional

The tolerance for the optimization: if the updates are smaller than tol, the optimization code checks the dual gap for optimality and continues until it is smaller than tol.

The default for tol is 0.0001 on my version of scikit-learn. I assume that your tolerance is so small that the optimization never reaches a lower value.

The only thing that SOMETIMES helped me to get rid of the warning was increasing the number of iterations significantly (with a significant increase of training time).

Increasing the tolerance always led to the same warnings, but with larger values in them, and not to getting rid of the warnings. Not sure why.

As an important analytical side note, I interpret getting this warning initially when using Lasso regression as a bad sign, regardless of what happens next.
For me it practically always occurred in the situation when the model was over-fitting, meaning that it performed well on the full training set itself, but then poorly during cross-validation and testing.
Regardless of whether I had supressed the warning (there is a way) or had gotten rid of it "naturally" by increasing the number of iterations, I almost always had to go back and simplify the set of features for Lasso to be effective (and in some cases to abandon Lasso altogether in favor of a different model).

I've got the same problem. Depending on the data variety, using the option normalize=True also help to make the model converge.