For reference - I've managed to find a way to do this.
As the relationship class is m-m and therefore the relationship has an intermediate table, I can query interface to get an ITable from the IRelationshipClass and then simply insert new relationships using ITable methods such as CreateRow(), SetValue() and Store(). As I thought, this performs much better than IRelationshipClass.CreateRelationship.
Hope that helps someone else out.
John