Dissolve will do what you want - combine the adjacent smaller shapes into one larger. Dissolve can be used with an attribute field (or more than one), such that it will only dissolve shapes that share the same value, but it can also just be run without attribute inputs in which case it dissolves touching geometry.
Whether or not you get one big polygon or several smaller ones depends on options when running the tool. One big polygon would be multi-part, meaning one database record but several disconnected geometries. Single-part polygons would be a single record for each individual geometry. Most dissolve tools have an option to allow multi-parts or not in the result. Even if you create them when you don't want to, there are other tools such as Explode or Multi-part to Singleparts that can separate them out.
I can't speak to the time issue when trying to run Dissolve in QGIS. Depending on how many polygons you have I wouldn't really expect it to run overnight. It's possible there may be geometry errors (you can run a check or validate geometry on the file before trying to dissolve) or other factors contributing to that issue.
In ArcGIS, with an Advanced license level there's also a tool called Aggregate Polygons that could be used to do what you want. There are also some less expensive add-ons with similar tools, such as ET GeoWizards.