It shouldbe your second option, Multipart to Single Part. Notice, however, that this will only work with Multilinestrings whose individual Linestrings are spatially connected. To be spatially connected means that either the start or the end point of a line shall have the same coordinates as either the start or end point of another line, as such:
# Line A and Line B are connected
Linestring A (0 0, 1 1)
Linestring B (1 1, 2 3)
# Line A and Line B are disconnected
Linestring A (0 0, 1 1)
Linestring B (1 2, 2 3)
What Multipart to Single Part does is transform your one multiline feature into one single line feature, but if the individual linestrings are disconnected, it can't return one single feature, thus it returns a multiline. There are two things you can do from here:
1. Your Multiline really should be only one linestring feature
This means you'll have to edit your data. In QGIS, go to Properties -> Styles, add another line style on top of your current one, and change it to Marker Style. Then set it to last vertex only, and change the shape of it from a ball to a sideways triangle.
With this, you know the start and end of each individual line in your multiline feature. Then check for the arrows along your line, these are the intersections. Edit the layer, with snap enabled, and make sure each point with a triangle properly connects to the first point of the next line. Only the first and last points of the entire multiline should not need be connected to anything. Then try the Mulyipart to Single Part again.
2. I don't care about the number of features, I just want simple Linestrings
This means a conversion from one Multiline feature to many single Line features. QGIS doesn't do this (afaik), but PostGIS does. You should already have it installed together with QGIS, so create a database, upload your layer (easiest done with QGIS' DB Manager plugin), then execute:
SELECT (ST_DUMP(geom).geom) as geom
FROM your_table_name
The result should be a bunch of binary-code features. These are your Linestrings in WKB format. Below the result panel there is an option to load the result back into QGIS. Just choose a layer name and click Load. Notice, however, that this loaded layer is virtual, you'll need to save it as a shapefile or sometging if you want to retain it after you quit QGIS.