"... but I don't see any reason why megaliths would have to require settlement or farming as a pre-cursor."
One of the initial factors was 'spare time'. When farming you have broader communities and can share the workload. Then occasionally you can all chip in and build a megalithic structure while the women are doing the weeding :-)