Is an atmega 2560 board compatible with the Adafruit Trellis?
MIDI comes in many different arrangements.

The two most important ones for you are "MIDI Over USB" and "Traditional Serial MIDI".

The former encapsulates MIDI messages and sends them over USB to the computer. This is what you normally get when you plug in a USB-based MIDI instrument, or a USB to MIDI adapter cable.

The latter is a simple serial port running at a specific baud rate. It's generally opto-isolated as well.

On the Leonardo you can do either of those methods (you haven't mentioned which you use), but on the ATMega2560 you can only do the latter (that is, connect the board to a USB to MIDI adaptor cable).  However the Arduino Mega2560 (Note: this is a board, what you talk about is a bare chip) has a USB interface chip that can be re-programmed to look like MIDI.  That will bridge between the "traditional serial MIDI" to the "MIDI over USB". However doing so may impare your ability to program the board.

Another option is to use some PC-based Serial-To-MIDI bridge software which reads normal Serial data as provided by the Arduino and converts it into MIDI signals within your computer. 

A third option is to step away from Arduino and choose a board that has both a native USB interface (with MIDI support in software) and more analog inputs.  A board such as one of the Teensy 3.x range would probably suit you well.