Ok interesting. So: it's a viable strategy, it's sortof already being done.
A key difference between the approach in the Harris/Singh paper and the proposal above is that the Harris/Singh paper proposes recompiling the program multiple times. The proposal above is taking a more vm approach, something like Java or C#, where the vm adapts continuously to the program's behavior during execution.
I suppose this does partly answer my question however about "how hard can this be?", in that a pre-requisite to do this is to make Haskell run as a vm?
To what extent is making Haskell run in a vm possible? To what extent does ghci attempt to do this/ meet the requirements for an efficient vm?
(off to read the rest of the paper, though everything after the abstract looks scary :-D )