//Get the GraphicsContainer
IGraphicsContainer graphicsContainer = axPageLayoutControl1.GraphicsContainer;

//Get the MapFrame
IMapFrame mapFrame = (IMapFrame)graphicsContainer.FindFrame(axPageLayoutControl1.ActiveView.FocusMap);
if (mapFrame == null) return;

//Create a legend
UID uID = new UIDClass();
uID.Value = "esriCarto.Legend";

//Create a MapSurroundFrame from the MapFrame
IMapSurroundFrame mapSurroundFrame = mapFrame.CreateSurroundFrame(uID, null);
if (mapSurroundFrame == null) return;
if (mapSurroundFrame.MapSurround == null) return;
//Set the name 
mapSurroundFrame.MapSurround.Name = "Legend";

//Envelope for the legend
IEnvelope envelope = new EnvelopeClass();
envelope.PutCoords(1, 1, 3.4, 2.4);

//Set the geometry of the MapSurroundFrame 
IElement element = (IElement)mapSurroundFrame;
element.Geometry = envelope;

//Add the legend to the PageLayout
axPageLayoutControl1.AddElement(element, Type.Missing, Type.Missing, "Legend", 0);

//Refresh the PageLayoutControl
axPageLayoutControl1.ActiveView.PartialRefresh(esriViewDrawPhase.esriViewGraphics, null, null);