How to remove all the polylines from a map

Keep track of the Polyline as you add it to the map:

Polyline polyline = this.mMap.addPolyline(new PolylineOptions().....);

Then when you want to remove it:

polyline.remove();

If you have lots of Polylines, just add them to a List as they are put on the map:

List<Polyline> polylines = new ArrayList<Polyline>();

for(....)
{
    polylines.add(this.mMap.addPolyline(new PolylineOptions()....));
}

And when you want to delete:

for(Polyline line : polylines)
{
    line.remove();
}

polylines.clear();

The key is to keep a reference to the Polyline objects and call .remove() on each one.