Emacs doesn't always properly translate modifiers on function keys.
First, see if the tmux option set -g xterm-keys on makes any difference. (This may require a new terminfo entry to fully work; if it makes any change at all even to say something other than ESC <up> please say in a comment)
Also, without xterm-keys on, try the key translations from this answer:
(define-key input-decode-map "\e\eOA" (kbd "<M-up>"))
(define-key input-decode-map "\e\eOB" (kbd "<M-down>"))
The xterm-keys solution has the advantage that, if it works, it will also work for shift and ctrl.
Instead of modifying the function-key-map, with xterm-keys on you can install a new terminfo entry with the appropriate keys:
# Note: tmux does translate Home and End (\EOH, \EOF) to \E[1~, \E[4~
# But leaves the modified versions (\E[1;?H etc) alone.
xterm+modkeys|xterm-style modifier keys,
kb2=\EOE, kent=\EOM,
kind=\E[1;2B, kri=\E[1;2A,
kf13=\E[1;2P, kf14=\E[1;2Q, kf15=\E[1;2R, kf16=\E[1;2S,
kf17=\E[15;2~, kf18=\E[17;2~, kf19=\E[18;2~, kf20=\E[19;2~,
kf21=\E[20;2~, kf22=\E[21;2~, kf23=\E[23;2~, kf24=\E[24;2~,
kf25=\E[1;5P, kf26=\E[1;5Q, kf27=\E[1;5R, kf28=\E[1;5S,
kf29=\E[15;5~, kf30=\E[17;5~, kf31=\E[18;5~, kf32=\E[19;5~,
kf33=\E[20;5~, kf34=\E[21;5~, kf35=\E[23;5~, kf36=\E[24;5~,
kf37=\E[1;6P, kf38=\E[1;6Q, kf39=\E[1;6R, kf40=\E[1;6S,
kf41=\E[15;6~, kf42=\E[17;6~, kf43=\E[18;6~, kf44=\E[19;6~,
kf45=\E[20;6~, kf46=\E[21;6~, kf47=\E[23;6~, kf48=\E[24;6~,
kf49=\E[1;3P, kf50=\E[1;3Q, kf51=\E[1;3R, kf52=\E[1;3S,
kf53=\E[15;3~, kf54=\E[17;3~, kf55=\E[18;3~, kf56=\E[19;3~,
kf57=\E[20;3~, kf58=\E[21;3~, kf59=\E[23;3~, kf60=\E[24;3~,
kf61=\E[1;4P, kf62=\E[1;4Q, kf63=\E[1;4R,
kDC=\E[3;2~, kDC3=\E[3;3~, kDC4=\E[3;4~, kDC5=\E[3;5~, kDC6=\E[3;6~, kDC7=\E[3;7~,
kDN=\E[1;2B, kDN3=\E[1;3B, kDN4=\E[1;4B, kDN5=\E[1;5B, kDN6=\E[1;6B, kDN7=\E[1;7B,
kEND=\E[1;2F, kEND3=\E[1;3F, kEND4=\E[1;4F, kEND5=\E[1;5F, kEND6=\E[1;6F, kEND7=\E[1;7F,
kHOM=\E[1;2H, kHOM3=\E[1;3H, kHOM4=\E[1;4H, kHOM5=\E[1;5H, kHOM6=\E[1;6H, kHOM7=\E[1;7H,
kIC=\E[2;2~, kIC3=\E[2;3~, kIC4=\E[2;4~, kIC5=\E[2;5~, kIC6=\E[2;6~, kIC7=\E[2;7~,
kLFT=\E[1;2D, kLFT3=\E[1;3D, kLFT4=\E[1;4D, kLFT5=\E[1;5D, kLFT6=\E[1;6D, kLFT7=\E[1;7D,
kNXT=\E[6;2~, kNXT3=\E[6;3~, kNXT4=\E[6;4~, kNXT5=\E[6;5~, kNXT6=\E[6;6~, kNXT7=\E[6;7~,
kPRV=\E[5;2~, kPRV3=\E[5;3~, kPRV4=\E[5;4~, kPRV5=\E[5;5~, kPRV6=\E[5;6~, kPRV7=\E[5;7~,
kRIT=\E[1;2C, kRIT3=\E[1;3C, kRIT4=\E[1;4C, kRIT5=\E[1;5C, kRIT6=\E[1;6C, kRIT7=\E[1;7C,
kUP=\E[1;2A, kUP3=\E[1;3A, kUP4=\E[1;4A, kUP5=\E[1;5A, kUP6=\E[1;6A, kUP7=\E[1;7A,
screen-xtermkeys|screen with xterm-style modifier keys,
use=xterm+modkeys, use=screen,
screen-xtermkeys-256color|screen with xterm keys and 256 colors,
use=xterm+modkeys, use=screen-256color,
tmux-xtermkeys|tmux with xterm-style modifier keys,
use=xterm+modkeys, use=tmux,
tmux-xtermkeys-256color|tmux with xterm keys and 256 colors,
use=xterm+modkeys, use=tmux-256color,
Compile with tic -x tmux-xtermkeys.ti and then set TERM to {tmux,screen}-xtermkeys{,-256color} as appropriate. I included screen for two reasons: First, emacs by default doesn't recognize tmux as a 256-color terminal. Second, some systems' version of the terminfo database is too old to include tmux information (remove these entries to get the file to compile).
It's better to use a screen terminfo entry than an xterm one because tmux used to recommend using screen and its emulation much more closely matches it. One thing you may notice in some circumstances is that text meant to be in standout mode will be in italics - if so, upgrade your terminfo data.
This will also work in other applications that support these keys (i.e. most places that they work now in xterm).
screen-xtermkeys-256colorandtmux-xtermkeys-256color. - Random832