Mutlicol is balancing its output and doing trial runs with different column breaks (at least at the end. For this it uses a different output routine. lineno is also installing its own output routine (by basically sending each line one by one to the OR to attach line numbers. The two do not know about each other and so conflict. To lineno, what multicol does looks like a single long column, so the attachment ends up on one side and the later cutting into columns just makes this wrong. But it would also a problem, because it is not clear what should be done if there are more than 2 columns produced by multicol.
Basically with both together, all you can do right now is to make the column separation large enough to allow the numbers there and have them always on the left or always on the right.