If you want to connect the Arduino Atmega2560 with ethernet, there are various options. The easiest might be to get a shield. The regular Arduino shield should fit on the Arduino Mega as well. there are 3 versions of the shield: with an ENC28J60, with a W5100 and with a W5500.
The shields are fairly expensive, it is cheaper to get an ethernet module. These are also available as ENC28J60, W5100 and W5500.
With prices all in the same range (currently around 2.60 Euro), it is best to get a W5500, the most modern chip of the range, that definitely needs less memory than the ENC28J60.
To connect it to an Arduino Mega2560, one only needs 7 connections as shown in the image below.
The SPI connections can be best taken from the ICSP connector and the chipselect from Pin 10.
Connections on the W5500 module are equally simple as they are usually printed on the module:
SCS is the chipselect that goes to pin 10
SCLK is the clock signal that goes to SCK on the 6 pin header.