Правильно: один миллион пятьсот тысяч пятисотый, две тысячи пятисотый. При склонении: один миллион пятьсот тысяч пятисотого, две тысячи пятисотого; один миллион пятьсот тысяч пятисотому, две тысячи пятисотому и т. д. В составных порядковых числительных изменяется только последнее слово.