In the Halachot of Boneh, constructing on Shabbat, the Poskim discuss whether building with Lego constitutes a prohibited type of building. Both Hacham Ovadia (Hazon Ovadia Shabbat Vol.5, p. 292) and Hacham Bension (Or Lesion Vol 2, Ch. 42:5) rule that children under Bar Misva may play with Lego, because it is considered a game, not real building, even if the child plans to keep the structure for a long time. If there is no issue in building, then there is also no problem to take apart already built structures.
This is the technical Halacha, but, of course, one should try to engage his children in Torah study on Shabbat as much as possible. Moreover, this leniency is only for children. Both Hachamim hold that these Lego pieces will be Mukse for an adult over Bar Misva.
SUMMARY
It is permissible for children under Bar Misva to build and take apart with Lego.
