Sim, é legal. A página que você vinculou diz o seguinte:
The F# redistributable package can be added to a deployment project to create a packaged, installable F# application that installs the F# runtime components when an application is installed on a client computer.
Você também pode verificar o arquivo redist.txt em [program files]\Microsoft Visual Studio 10.0\ (ou 9.0 se estiver executando 2008). Você tem permissão para redistribuir as bibliotecas listadas nesse arquivo e quando tiver o F # instalado, FSharp.Core.dll deve estar nessa lista.